建个正向的图。
建个反向的图。
2遍spfa搞定。
#include<cstdio> #include<iostream> #include<cstring> #include<queue> #include<algorithm> using namespace std; int p,q; const int inf=0x3f3f3f3f; struct node { int v,nxt; int w; }edge[1000005]; struct s{ int a,b,c; }record[1000005]; int nume,head[1000005]; int dis[1000005]; int inque[1000005]; void add(int u,int v,int w) { edge[nume].v=v;edge[nume].w=w;edge[nume].nxt=head[u]; head[u]=nume++; } int ans=0; void spfa(int src){ int i; queue<int >que; que.push(src); for(i=1;i<=p;i++) { dis[i]=inf; inque[i]=0; } dis[src]=0; inque[src]=1; while(!que.empty()){ int u=que.front(); que.pop(); inque[u]=0; for(i=head[u]; i!=-1 ; i=edge[i].nxt){ int v=edge[i].v; if(dis[u]+edge[i].w<dis[v]){ dis[v]=dis[u]+edge[i].w; if(!inque[v]){ que.push(v); inque[v]=1; } } } } } int main() { int t; scanf("%d",&t); while(scanf("%d%d",&p,&q)!=EOF){ int i; nume=0; memset(head,-1,sizeof(head)); for(i=0;i<q;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); record[i].a=a;record[i].b=b;record[i].c=c; add(a,b,c); } ans=0; spfa(1); for(i=2;i<=p;i++) ans+=dis[i]; nume=0; memset(head,-1,sizeof(head)); for(i=0;i<q;i++){ add(record[i].b,record[i].a,record[i].c); } spfa(1); for(i=2;i<=p;i++) ans+=dis[i]; printf("%d\n",ans); } }
原文:http://blog.csdn.net/cnh294141800/article/details/23207749