4639992_ac_79ms_236k.cpp

来自「部分PKU上的源码」· C++ 代码 · 共 64 行

//#include <stdio.h> 
#include <string>
#include <iostream> 
//#define max 10001 
//#define point 501 
using namespace std;
struct E{ 
    int u, v, w; 
}e[25000];
 int el, n, d[501];
 
 void bellman(){
     int i, j, f = 0;
     for(i = 0; i < n - 1; i++){
         f = 0;
         for(j = 0; j < el; j++){
             if(d[e[j].v] > d[e[j].u] + e[j].w){
                 d[e[j].v] = d[e[j].u] + e[j].w;
                 f = 1;
             }
         }
         if(!f){
             puts("NO");
             return;
         }
     }
     for(i = 0; i < el; i++){
         if(d[e[i].v] > d[e[i].u] + e[i].w){
             puts("YES");
             return;
         }
     }
     puts("NO");
 }
 
 int main(){
     int i, m, w, u, v, W, F;
     scanf("%d", &F);
     while(F--){
         el = 0;
		 
         scanf("%d%d%d", &n, &m, &w);
         for(i = 0; i < m; i++){
             scanf("%d%d%d", &u, &v, &W);
             e[el].u = u;
             e[el].v = v;
             e[el++].w = W;
             e[el].u = v;
             e[el].v = u;
             e[el++].w = W;
         }
         for(i = 0; i < w; i++){
             scanf("%d%d%d", &u, &v, &W);
             e[el].u = u;
             e[el].v = v;
             e[el++].w = -W;
         }
         bellman();
     }
     return 0;
 }