false, sizeof(vis)); for(int i = 0; i <= p; i++) dist[i] = INF; dist[v0] = 0; queue
Q; Q.push(v0); while(!Q.empty()) { int u = Q.front(); Q.pop(); vis[u] = false; int sz = vt[u].size(); for(int i = 0; i < sz; i++) { int v = vt[u][i].v; int w = vt[u][i].w; if(dist[v] > dist[u] + w) { dist[v] = dist[u] + w; if(!vis[v]) { Q.push(v); vis[v] = true; } } } } } void Clear() { for(int i = 1; i <= p; i++) vt[i].clear(); } int main() { int T; scanf("%d", &T); while(T--) { ans = 0; scanf("%d %d", &p, &q); for(int i = 0; i < q; i++) scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w); Clear(); for(int i = 0; i < q; i++) vt[e[i].u].push_back(NODE(e[i].v, e[i].w)); SPFA(1); for(int i = 1; i <= p; i++) ans += dist[i]; Clear(); for(int i = 0; i < q; i++) vt[e[i].v].push_back(NODE(e[i].u, e[i].w)); SPFA(1); for(int i = 1; i <= p; i++) ans += dist[i]; printf("%d\n", ans); } }
|