题目大意：有编号从一号到n号的n个点，m条路，问从一号到其他点，再从其他点回到一号，每个点都要走一次，问总路程最短多少。
解题思路：因为数据量很大，用一般的dijkstra的话，二维数组也太大了，开不了。所以用spfa求。首先要学用邻接表示图，这样省空间，省时间，先看这篇博客学习一下（http://ahalei.blog.51cto.com/4767671/1391988）然后spfa的方法就是，首先将起点入队列，在队列空时退出循环，循环内，“”每次取队首，去队首，判断与‘取出的队首’相关的路，进行松弛，如果松弛成功并且‘用于松弛的点’未在队列内，则将‘用于松弛的点’入列。”这样最后就是最短路了。因为是有向图，所以从其他点到一号时，不能简单的乘两倍，而是要将道路反向，再进行一次spfa。如刚开始1->2 5，反向后，2->1 5，反向的结果就是本是“从A点出发到B点的”改变为“从B点前往A点”，这就使得原本“从其他点到起点”就改变为“起点到其他点”，这样进行松弛就没问题了。否则求其他点回到一号时，一共有n-1个起点得求n-1次spfa，会爆炸吧。最后就是题目input中的“
the sum of which is smaller than 1000000000. ”应该是指每条路长，所以结果得用long long存
ac代码：
#include <iostream>
#include <cstring>
#include <queue>
#define N 1000005
#define inf 1000000005
using namespace std;
queue <int>qu;
int t, n, m, first[N], next[N], dis[N];
int u[N], v[N], w[N], vis[N], temp;
long long sum;
void init()
{sum = 0;for (int i=1; i<=n; i++){first[i] = -1; dis[i] = inf;}memset(vis, 0, sizeof(vis));dis[1] = 0;for (int i=1; i<=m; i++){scanf("%d%d%d", &u[i], &v[i], &w[i]);next[i] = first[u[i]];first[u[i]] = i;}
}
void spfa()
{int s, p, k;while (!qu.empty())qu.pop();qu.push(1);while (!qu.empty()){s = qu.front();qu.pop();vis[s] = 0;p = first[s];while (p != -1){k = v[p];if (dis[k] > dis[s] + w[p]){dis[k] = dis[s] + w[p];if (!vis[k]){vis[k] = 1;qu.push(k);}}p = next[p];}}
}
int main()
{scanf("%d", &t);while (t--){scanf("%d%d", &n, &m);init();spfa();for (int i=2; i<=n; i++)sum += dis[i];for (int i=1; i<=n; i++){first[i] = -1;dis[i] = inf;}dis[1] = 0;for (int i=1; i<=m; i++){temp = u[i];u[i] = v[i];v[i] = temp;next[i] = first[u[i]];first[u[i]] = i; }memset(vis, 0, sizeof(vis));spfa();for (int i=2; i<=n; i++)sum += dis[i];printf("%lld\n", sum);}
return 0;
}