题意：
给出P个人P个车站Q条路，每条路都是有向的。
然后问你从1出发到达点（2-N）再从点（2-N）回来的最短总距离。
思路：
先对点1到（2-N）求一次最短路，可以得出点1到所有点的距离。
然后再对反图从点1到(2-N)求一次最短路，可以求出所有点（2-N）到点1的距离。
相加结果即为最短的路程。
解题过程：
其实思路很简单，因为注意到数据量实在太大了，10^6的点，所以邻接矩阵是不可能的。
用vector果断超时，所以用邻接表表示。反图的话只要首位点反一下即可。
但是这题最难的地方其实完全不是敲代码的过程。
Prices are positive integers the sum of which is smaller than 1000000000。
千万别被这句话骗了，最后的sum是64位的。。
这应该是本题最坑的地方了。
/*
Memory: 36988KTime: 1813MS Language: G++ Result: Accepted
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 10000005
#define inf 1000000005
#define INF 1<<30
using namespace std;
int P,Q;
bool visit[Max];
__int64 dis[Max];
void spfa(int *u,int *v,int *w,int *head,int *next)
{
int i,j;
queue<int>q;
visit[1]=1;
for(i=1; i<=P; i++)
dis[i]=inf;//初始化的这个值注意。。要大一点。。这里粗心WA了好几次
dis[1]=0;
q.push(1);
while(!q.empty())
{
int temp=q.front();
q.pop();
visit[temp]=0;
for(i=head[temp]; i>=0; i=next[i])
{
if(dis[v[i]]>dis[temp]+w[i])
{
dis[v[i]]=dis[temp]+w[i];
if(!visit[v[i]])
{
q.push(v[i]);
visit[v[i]]=1;
}
}
}
}
}
int u[Max],v[Max],w[Max],head[Max],next[Max];
int head1[Max],next1[Max];
int main()
{
int i,j,k,l,n,m,T;
int x,y,fee;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&P,&Q);
for(i=0;i<=P;i++)
{
head[i]=-1;
head1[i]=-1;
}
for(i=0; i<Q; i++)
{
scanf("%d%d%d",&u[i],&v[i],&w[i]);
next[i]=head[u[i]];
head[u[i]]=i;//正图
next1[i]=head1[v[i]];//逆图
head1[v[i]]=i;
}
spfa(u,v,w,head,next);//对正图求最短路
__int64 sum=0;//sum。。。。
for(i=1; i<=P; i++)
sum+=dis[i];
spfa(v,u,w,head1,next1);//对逆图求最短路
for(i=1; i<=P; i++)
sum+=dis[i];
cout<<sum<<endl;
}
return 0;
}
做完的感觉就是。。。这题好坑啊。。