leetcode-go/poj/3259.wormholes/main.cc

#include <cstdio>
#include <cstring>

using namespace std;

const int N = 500;
const int M = 2500;
const int W = 200;
const int INF = 0x3F3F3F3F;

int dist[N + 1];

struct E {
  int s;
  int e;
  int t;
  E(int s = 0, int e = 0, int t = 0) : s(s), e(e), t(t) {}
} edge[2 * M + W];

int main() {
  int f, n, m, w, s, e, t, k;
  scanf("%d", &f);
  while (f--) {
    scanf("%d %d %d", &n, &m, &w);
    k = 0;
    for (int i = 0; i < m; i++) {
      scanf("%d %d %d", &s, &e, &t);
      edge[k].s = s;
      edge[k].e = e;
      edge[k++].t = t;
      edge[k].s = e;
      edge[k].e = s;
      edge[k++].t = t;
    }
    for (int i = 0; i < w; i++) {
      scanf("%d %d %d", &s, &e, &t);
      edge[k].s = s;
      edge[k].e = e;
      edge[k++].t = -t;
    }
    memset(dist, 0x3F, sizeof(dist));
    dist[1] = 0;
    for (int i = 1; i < n; i++) {  // Passes no more than i edges
      for (int j = 0; j < k; j++) {
        s = edge[j].s;
        e = edge[j].e;
        if (edge[j].t + dist[s] < dist[e]) dist[e] = edge[j].t + dist[s];
      }
    }
    int i;
    for (i = 0; i < k; i++) {
      s = edge[i].s;
      e = edge[i].e;
      if (edge[i].t + dist[s] < dist[e]) break;
    }
    if (i < k)
      printf("YES\n");
    else
      printf("NO\n");
  }
  return 0;
}