POJ(PKU) 3259 Wormholes

ベルマンフォード法で負閉路の検出をするだけ。

細かいところは問題文参照してください。

#include <cstdio>
#include <algorithm>
#include <string.h>

using namespace std;

const int MAX_E = 6000;
const int MAX_V = 600;

const int INF = 100000000;



struct edge { int from,to,cost; };

edge es[MAX_E];

int d[MAX_V];
int V,E;

bool find_negative_loop(){
  memset(d, 0, sizeof(d));
  
  for(int i = 0;i < V;i++){
    for(int j = 0;j < E;j++){
      edge e = es[j];
      if(d[e.to] > d[e.from] + e.cost){
	d[e.to] = d[e.from] + e.cost;

	if(i == V - 1) return true;
      }
    }
  }
  return false;
}
 int main(){
   
int f;

scanf("%d",&f);

while(f--){
  int n,m,w;
  int co = 0;
  scanf("%d%d%d",&n,&m,&w);
  V = n;
  
  while(m--){
    int s,e,t;
    scanf("%d%d%d",&s,&e,&t);
    
    edge tmp = {s,e,t};
    es[co++] = tmp;
    edge tmp2 = {e,s,t};
    es[co++] = tmp2;
  }
  
  while(w--){
    int s,e,t;
    scanf("%d%d%d",&s,&e,&t);
    
    edge tmp = {s,e,-t};
    es[co++] = tmp;
  }
  
  E = co;
  
  if(find_negative_loop()){
    printf("YES\n");
  }else{
    printf("NO\n");
  }
  
}

return 0;
}