HDU-1535-.zip_多源点

/**** 有向边，求单源点到所有点的最短路，直接SPFA 求多源点到单终点的最短路，反向建图，就变成 单源点到多终点的最短路问题 */ #include <stdio.h> #include <string.h> #include <stdlib.h> #include <algorithm> #include <vector> #include <queue> using namespace std; const int maxn = 1000100; const int inf = 0x3f3f3f3f; struct Edge{ int from, to, weight; }; int n, m; vector<Edge> edges, edges1; vector<int> G1[maxn], G2[maxn]; int inq[maxn], d2[maxn], d1[maxn]; void addedge(int from, int to, int weight){ edges.push_back((Edge){from, to, weight}); int m = edges.size(); G1[from].push_back(m - 1); edges1.push_back((Edge){to, from, weight}); m = edges1.size(); G2[to].push_back(m - 1); } void init(){ edges.clear(); edges1.clear(); for(int i = 0; i <= n; i ++){ G1[i].clear(); G2[i].clear(); } } void spfa1(int s, int t){ queue<int> q; for(int i = 0; i <= n; i ++){ d1[i] = inf; inq[i] = false; } d1[s] = 0; inq[s] = true; q.push(s); while(!q.empty()){ int u = q.front(); q.pop(); inq[u] = false; for(int i = 0; i < G1[u].size(); i ++){ Edge& e = edges[G1[u][i]]; int v = e.to; if(d1[u] + e.weight < d1[v]){ d1[v] = d1[u] + e.weight; if(!inq[v]){ inq[v] = true; q.push(v); } } } } } void spfa2(int s, int t){ queue<int> q; for(int i = 0; i <= n; i ++){ d2[i] = inf; inq[i] = false; } d2[s] = 0; inq[s] = true; q.push(s); while(!q.empty()){ int u = q.front(); q.pop(); inq[u] = false; for(int i = 0; i < G2[u].size(); i ++){ Edge& e = edges1[G2[u][i]]; int v = e.to; if(d2[u] + e.weight < d2[v]){ d2[v] = d2[u] + e.weight; if(!inq[v]){ inq[v] = true; q.push(v); } } } } } int main() { int T; scanf("%d", &T); while(T --){ scanf("%d%d", &n, &m); init(); while(m --){ int u, v, w; scanf("%d%d%d", &u, &v, &w); addedge(u, v, w); } int ans = 0; spfa1(1, n); spfa2(1, n); for(int i = 2; i <= n; i ++){ ans += d1[i]; ans += d2[i]; } printf("%d\n", ans); } return 0; }