题目描述
在电视时代,没有多少人观看戏剧表演。Malidinesia古董喜剧演员意识到这一事实，他们想宣传剧院,尤其是古色古香的喜剧片。他们已经打印请帖和所有必要的信息和计划。许多学生被雇来分发这些请柬。每个学生志愿者被指定一个确切的公共汽车站，他或她将留在那里一整天,邀请人们参与。
这里的公交系统是非常特殊的:所有的线路都是单向的，连接两个站点。公共汽车离开起始点，到达目的地之后又空车返回起始点。学生每天早上从总部出发，乘公交车到一个预定的站点邀请乘客。每个站点都被安排了一名学生。在一天结束的时候,所有的学生都回到总部。现在需要知道的是，学生所需的公交费用的总和最小是多少。
输入输出格式
输入格式：
第1行有两个整数n、m(1<=n,m<=1000000)，n是站点的个数，m是线路的个数。
然后有m行，每行描述一个线路，包括3个整数，起始点，目的地和价格。
总部在第1个站点，价钱都是整数，且小于1000000000。
输出格式：
输出一行，表示最小费用。
输入输出样例
输入样例#1：
4 6 1 2 10 2 1 60 1 3 20 3 4 10 2 4 5 4 1 50
输出样例#1：
210
说明
【注意】
此题数据规模较大，需要使用较为高效的算法，此题不设小规模数据分数。
代码：
1 //单向边建立一个图，spfa计算出1到所有点的最短距离 2 //再建立一个反向图，spfa计算出其他各点到1的最短距离。 3 #include<cstdio> 4 #include<cstring> 5 using namespace std; 6 const int N=1000005,INF=0x3f3f3f3f; 7 8 int n,m,cnt,x[N],y[N],z[N],H[N<<1],Q[N+10]; 9 long long Ans,Dist[N]; 10 bool vis[N]; 11 struct Edge 12 { 13 int to,val,nxt; 14 }e[N<<1]; 15 16 void read(int &now) 17 { 18 now=0;char c=getchar(); 19 while(c>'9'||c<'0')c=getchar(); 20 while(c>='0'&&c<='9')now=(now<<3)+(now<<1)+c-'0',c=getchar(); 21 } 22 23 void AddEdge(int u,int v,int w) 24 { 25 e[++cnt].to = v; 26 e[cnt].val = w; 27 e[cnt].nxt = H[u]; 28 H[u] = cnt; 29 } 30 31 void SPFA(int x) 32 { 33 memset(vis,0,sizeof vis); 34 memset(Dist,INF,sizeof Dist); 35 vis[x]=1; 36 Dist[x]=0; 37 int h=0,t=1; 38 Q[h]=1; 39 while(h<t) 40 { 41 int cur=Q[h++]; 42 vis[cur]=0; 43 for(int i=H[cur];i;i=e[i].nxt) 44 { 45 int to=e[i].to,v=e[i].val; 46 if(Dist[to]>Dist[cur]+v) 47 { 48 Dist[to]=Dist[cur]+v; 49 if(!vis[to]) 50 Q[t++]=to,vis[to]=1; 51 } 52 } 53 } 54 } 55 56 int main() 57 { 58 read(n);read(m); 59 for(int i=1;i<=m;++i) 60 read(x[i]),read(y[i]),read(z[i]),AddEdge(x[i],y[i],z[i]); 61 SPFA(1); 62 for(int i=2;i<=n;++i) 63 Ans+=Dist[i]; 64 memset(H,0,sizeof H); 65 cnt=0; 66 for(int i=1;i<=m;++i) 67 AddEdge(y[i],x[i],z[i]); 68 SPFA(1); 69 for(int i=2;i<=n;++i) 70 Ans+=Dist[i]; 71 printf("%lld",Ans); 72 return 0; 73 }