题意：
t组样例。
每组有n个节点，有m条单向边。
有m组输入，每组a b c 表示从a到b的单向边的权值是c。
求解，从编号为1的节点出发，有n-1个人，要求他们分别到达编号从2到n的节点再返回，所有边的权值的和最小是多少。
思路：
构图，构两个图，分别是正向图和反向图，然后用dij算单源最短路，将所有点到1的最短路加起来就是答案。
这题注意
1.inf原先的99999999定义不够大。
2.需要用到优先队列优化。
3.vector会超时，需要写手工邻接表。
4.一开始看到网上有人写getint();这样的函数发现在这道题并不能缩短时间，直接用scanf时间是1600，用了getint();时间是3200.
/************************************************************************* > File Name: B.cpp > Author: ttpond > Created Time: 2015-8-18 16:47:3 ************************************************************************/ #include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<math.h> #include<vector> #include<map> #include<queue> #include<stack> #include<set> using namespace std; int ednum; struct st { int id,dis; st(int a,int b) { id=a; dis=b; } st(){}; }; struct cmp { bool operator()(const st &a,const st &b) { return a.dis>b.dis; } }; struct edge { int id,w; edge *next; }; edge *adj[2][1000010]; edge edges[2][1000010]; int dis[1000010]; inline void addEdge(int a,int b,int c) { edge *aa,*bb; aa=&edges[0][ednum]; bb=&edges[1][ednum]; ednum++; aa->id=b; aa->w=c; aa->next=adj[0][a]; adj[0][a]=aa; bb->id=a; bb->w=c; bb->next=adj[1][b]; adj[1][b]=bb; } int n,m; const int inf=1999999999; int dis1[1000050]; void dfs(int num) { for(int i=1;i<=n;i++) { dis[i]=inf; } priority_queue<st,vector<st>,cmp>q; st tmp; dis[1]=0; q.push(st(1,0)); while(!q.empty()) { tmp=q.top(); q.pop(); for(edge *p=adj[num][tmp.id];p;p=p->next) { if(dis[p->id]>p->w+dis[tmp.id]) { dis[p->id]=p->w+dis[tmp.id]; q.push(st(p->id,dis[p->id])); } } } }int main() { int t,tt; scanf("%d",&t); int a,b,c,d; //cout<<inf; for(tt=0; tt<t; tt++) { ednum=0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { for(int j=0;j<2;j++) { adj[j][i]=NULL; } } for(int i=0; i<m; i++) { scanf("%d%d%d",&a,&b,&c); addEdge(a,b,c); } long long ans=0; for(int i=0;i<2;i++) { dfs(i); for(int i=1;i<=n;i++) { ans+=dis[i]; } } printf("%I64d ",ans); } }