题意：给你n个点的有向图，从1点到其他所有点又从其他点回到1点的最短路。
思路：可以求一次从1点出发的最短路，再反向建图，再求一次从1出发的最短路，把两次的结果加起来就是题目所求。由于边比较多，
所以最好用Dijkstra+优先队列，或者SPFA；
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
const int maxn = 1000009;
const int inf = 1<<30;
#include<vector>
struct node
{
int v,w;
node(int v,int w):v(v),w(w){}
bool operator < (const node a)const
{
return w > a.w;
}
};
std::vector<node> eg[maxn];
std::priority_queue<node> q;
int n,m;
int vis[maxn];
int dis[maxn];
int a[maxn],b[maxn],c[maxn];
void DIJ()
{
int i;
memset(vis,0,sizeof(vis));
for(i=0;i<=n;i++)
dis[i] = inf;
while(!q.empty())q.pop();
dis[1] = 0;
vis[1] = 0;
int size = eg[1].size();
for(i=0; i < size; i++)
{
q.push(node(eg[1][i].v,eg[1][i].w));
dis[eg[1][i].v] = eg[1][i].w;
}
while(!q.empty())
{
int u = q.top().v;
int w = q.top().w;
q.pop();
if(!vis[u])
{
vis[u] = 1;
size = eg[u].size();
for(i=0; i<size; i++)
{
int v = eg[u][i].v;
int w = eg[u][i].w;
if(!vis[v] && dis[u] + w < dis[v])
{
dis[v] = dis[u] + w;
q.push(node(v,dis[v]));
}
}
}
}
}
void work()
{
int i,sum = 0;
DIJ();
for(i=2; i<=n; i++) sum += dis[i]; //printf("%d ",dis[i]);}
for(i=0; i<=n; i++) eg[i].clear();
for(i=0;i<m;i++) eg[b[i]].push_back(node(a[i],c[i]));
// printf("
");
DIJ();
for(i=2; i <= n;i++) sum += dis[i]; //printf("%d ",dis[i]);}
printf("%d
",sum);
}
void input()
{
int i;
scanf("%d%d",&n,&m);
for(i=0 ;i < m; i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
for(i=0;i<=n;i++) eg[i].clear();
for(i=0;i<m;i++) eg[a[i]].push_back(node(b[i],c[i]));
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
input();
work();
}
return 0;
}
/*
3
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50
2 2
1 2 13
2 1 33
*/