题目的大意是在有向加权图中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;
}
