백준[1865] 웜홀

문제 설명

문제 링크

http://icpc.me/1865

1865번: 웜홀

풀이

플로이드 와샬을 이용하면 O(N^3)에 풀 수 있다.

플로이드 와샬을 돌린 후 dp[i][i]에 음수가 있는지 체크하면 된다.

코드

 

#include <bits/stdc++.h>
using namespace std;

const int N = 502;
const int INF = 1e8;
int dp[N][N];

int main() {
    int tc; scanf("%d", &tc);
    while (tc--) {
        int n, m, w; scanf("%d %d %d", &n, &m, &w);
        for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dp[i][j] = INF;

        while (m--) {
            int s, e, t; scanf("%d %d %d", &s, &e, &t);
            dp[s][e] = min(dp[s][e], t);
            dp[e][s] = min(dp[e][s], t);
        }
        while (w--) {
            int s, e, t; scanf("%d %d %d", &s, &e, &t);
            dp[s][e] = -t;            
        }

        for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) {
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);            
        }
        bool flag = false;
        for (int i = 1; i <= n; i++) if (dp[i][i] < 0) flag = true;
        printf("%s\n", flag ? "YES" : "NO");
    }
}