?

之前一开始 ，没做出来，搁置了好几天才看见bug所在。所以今天a掉了 ，把代码贴出来，这个使用邻接矩阵表示的 ，下一篇用邻接表可以提高效率。

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; const int INF=600; int G[INF][INF]; int inq[INF]; int res[INF]; int dict[INF]; int n,m,w; bool spfa(int x) { queue
      
       cnt; memset(dict,0,sizeof(dict)); cnt.push(x); memset(res,0x1f,sizeof(res)); memset(inq,0,sizeof(inq)); res[x]=0; dict[x]++; while(!cnt.empty()) { int cur=cnt.front(); cnt.pop(); inq[cur]=0; for(int i=1; i<=n; i++) { if(res[i]>res[cur]+G[cur][i]) { res[i]=res[cur]+G[cur][i]; if(!inq[i]) { cnt.push(i); inq[i]=1; if(++dict[i]>=n) return 1; } } } } return 0; } int main() { int s,e,t; int T; cin>>T; while(T--) { cin>>n>>m>>w; memset(G,0x1f,sizeof(G)); int k; for(int i=0; i
       
        >s>>e>>t; G[s][e]=G[e][s]= G[e][s]>t? t:G[s][e]; k=s; } for(int j=0; j
        
         >s>>e>>t; G[s][e]=G[s][e]>-t?-t : G[s][e]; } printf(%s ,spfa(1)?YES:NO); } return 0; } 
        
       
      
     
    
   
  

?