POJ 3259 Wormholes(Floyd判负环)

#include <iostream>
#include <cstdio>
#include <cstring>
#define inf 0x3f3f3f3f
#define maxn 505
using namespace std;
int T,n,m,k;
int pre[maxn][maxn];

void init(){
  for(int i=0;i<=n;i++){
    for(int j=0;j<=n;j++){
      if(i == j)pre[i][j] = 0;
      pre[i][j] = pre[j][i] = inf;
    }
  }
}

bool floyd(){
  for(int k=1;k<=n;k++){
    for(int i=1;i<=n;i++){
      for(int j=1;j<=n;j++){
        if(pre[i][j] > pre[i][k] + pre[k][j]){
          pre[i][j] = pre[i][k] + pre[k][j];
        }
      }
      if(pre[i][i] < 0)return true;
    }
  }
  return false;
}

int main()
{
  scanf("%d",&T);
  while(T--){
    scanf("%d%d%d",&n,&m,&k);
    init();
    while(m--){
      int u,v,l;
      scanf("%d%d%d",&u,&v,&l);
      if(l < pre[u][v])
      pre[u][v] = pre[v][u] = l;
    }
    while(k--){
      int u,v,l;
      scanf("%d%d%d",&u,&v,&l);
      pre[u][v] = -l;
    }
    if(floyd()) puts("YES");
    else puts("NO");
  }
  return 0;
}