1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78
| #include <cstring> #include <utility> #include <cstdio> #include <queue> using namespace std; const int N=10000,INF=1e9;
int Head[N],Edge[N],Leng[N],Next[N],tot; long long H[N],C[N],Dis[N]; bool V[N]; int n,m; inline void addedge(int u,int v,int w){ Edge[++tot]=v,Leng[tot]=w,Next[tot]=Head[u],Head[u]=tot; }
inline bool spfa(int s){ queue<int> q; memset(H,0x3f,sizeof(H)); memset(V,false,sizeof(V)); H[s]=0,V[s]=true,q.push(s); while(!q.empty()){ int x=q.front(); q.pop(); V[x]=false; for(int i=Head[x]; i; i=Next[i]){ int y=Edge[i],z=Leng[i]; if(H[y]>H[x]+z){ H[y]=H[x]+z; if(!V[y]){ V[y]=true,q.push(y),++C[y]; if(C[y]>n) return false; } } } } return true; }
inline void dijkstra(int s){ priority_queue<pair<int,int> > q; for(int i=1; i<=n; ++i) Dis[i]=INF; memset(V,false,sizeof(V)); Dis[s]=0,q.push(make_pair(0,s)); while(!q.empty()){ int x=q.top().second; q.pop(); if(V[x]) continue; V[x]=true; for(int i=Head[x]; i; i=Next[i]){ int y=Edge[i],z=Leng[i]; if(Dis[y]>Dis[x]+z){ Dis[y]=Dis[x]+z; if(!V[y]) q.push(make_pair(-Dis[y],y)); } } } return; }
int main(){ scanf("%d%d",&n,&m); for(int i=1; i<=m; ++i){ int x,y,z; scanf("%d%d%d",&x,&y,&z); addedge(x,y,z); } for(int i=1; i<=n; ++i) addedge(0,i,0); if(!spfa(0)) return puts("-1")&0; for(int i=1; i<=n; ++i) for(int j=Head[i]; j; j=Next[j]) Leng[j]=Leng[j]+H[i]-H[Edge[j]]; for(int i=1; i<=n; ++i){ dijkstra(i); long long ans=0; for(int j=1; j<=n; ++j) ans+=j*(Dis[j]==INF ? INF : Dis[j]-H[i]+H[j]); printf("%lld\n",ans); } return 0; }
|