SPFA.rar_SPFA_problem solving

题目的大意是在有向加权图中G（V，E），邮局要从起点S向其他n个节点发送邮件，于是派出n个邮递员，分别到达其他n个地点发送，然后回到起点S，求出所有邮递员所经过的总路程的最小值。明显这是一个单源最短路径的问题。思路很清晰，先正向建边求一次最短路径，得sum1；再反向建边求一次最短路径，得sum2。答案就是sum1+sum2。 问题在于，题目给出的规模很吓人，顶点和边的数目在1000000以内。假如用邻接矩阵必定MLE，用普通的Dijkstra也必定会TLE。所以我们必须使用最优化的最短路算法。 下面这个代码求最短路的算法是SPFA，而图则用前向星来存储。其中明细不甚明白，这毕竟只是一个模板。建了两个图，一个是正向图，一个是反向图，分别两次调用spfa函数就可以求最短路。最后累加即可。 另外要注意，POJ对原题加了数据，因此很多Pascal写的标程在POJ上都会WA，估计是发生溢出了。此题中间处理的数字会超过1000000000。因此处理路径的变量需要用long long。在ZOJ上就没有加数据，正常的程序都能过。 SPFA的效率还是可以的，这个程序运行大概需要2000ms，可以接受。提交时语言要选C++。 #include <cstdio> #include <cstring> #include <queue> using namespace std; #define N 1000005 #define MAXF 1000000000 struct edge { int a, b; int w; int next; edge(int aa, int bb, int ww, int nn) { a = aa; b = bb; w = ww; next = nn; } edge() { } }; edge ET1[N], ET2[N]; int EH1[N], EH2[N], n; long long dist[N]; bool inQ[N]; void spfa(int s, int *EH, edge *ET) { queue<int> Q; memset(inQ, 0, sizeof(inQ)); fill(dist, dist + N, MAXF); dist[s] = 0; inQ[s] = 1; Q.push(s); while (!Q.empty()) { int k = Q.front(); Q.pop(); inQ[k] = 0; for (int p = EH[k]; p != -1; p = ET[p].next) { long long t = ET[p].b, w = ET[p].w; if (dist[k] + w < dist[t]) { dist[t] = dist[k] + w; if (!inQ[t]) { inQ[t] = 1; Q.push(t); } } } } } void addedge(int a, int b, int w, int *tot, edge *ET, int *EH) { ET[*tot] = edge(a, b, w, EH[a]); EH[a] = *tot; (*tot)++; } void solve() { int m, i, a, b, w, tot1, tot2; long long sum = 0; memset(EH1, -1, sizeof EH1); memset(EH2, -1, sizeof EH2); tot1 = tot2 = 0; scanf("%d %d", &n, &m); for (i = 0; i < m; i++) { /* 分别建立正向和反向图 */ scanf("%d %d %d", &a, &b, &w); addedge(a, b, w, &tot1, ET1, EH1); addedge(b, a, w, &tot2, ET2, EH2); } /* 分两次调用spfa，累加其结果 */ spfa(1, EH1, ET1); for (i = 1; i <= n; i++) sum += dist[i]; spfa(1, EH2, ET2); for (i = 1; i <= n; i++) sum += dist[i]; printf("%lld\n", sum); } int main() { int T; scanf("%d", &T); while (T--) solve(); return 0; }