POJ3259--Wormholes(bellman).rar_wormhole code _wormholes

#include<iostream> #define INF 1<<14 using namespace std; struct{ int start,destination; int time; }edge[50000]; bool bellman_ford(int s,int N,int M,int W) { int d[20000]; bool flag=true; for(int i=0;i<=N;i++)d[i]=INF; d[s]=0; for(int i=1;i<=N&&flag==true;i++) { flag=false; for(int j=0;j<=M*2+W-1;j++) if(d[edge[j].destination]>d[edge[j].start]+edge[j].time) { d[edge[j].destination]=d[edge[j].start]+edge[j].time; flag=true; } } if(flag==true) return true; else return false; } int main() { int F,N,M,W; int S,E,T; cin>>F; while(F--) { cin>>N>>M>>W; for(int i=0;i<=M-1;i++) { cin>>S>>E>>T; edge[i*2].start=S;edge[i*2].destination=E;edge[i*2].time=T; edge[i*2+1].start=E;edge[i*2+1].destination=S;edge[i*2+1].time=T; } for(int i=M*2;i<=M*2+W-1;i++) { cin>>S>>E>>T; edge[i].start=S;edge[i].destination=E;edge[i].time=-T; } if(bellman_ford(1,N,M,W)) cout<<"YES"<<endl; else cout<<"NO"<<endl; } system("pause"); return 0; }