BOJ)1865 웜홀

문제: icpc.me/1865

방향 그래프에서 시간이 거꾸로 간다는 개념이 나온다면 우선 벨만-포드를 생각해 볼 수 있다.

이때 주의 할 점은 도로는 방향이 없으므로 양 방향에 연결을 해줘야 한다. 

문제에서 질문은 출발을 하였을 때 보다 시간이 되돌아 가 있는 경우가 있는지 확인하는 것인데 

이것은 벨만-포드에서 음수 사이클 존재 여부를 확인하는 것과 동치다.

따라서 벨만-포드를 구현 한 뒤 음수 사이클 존재 여부에 따라 출력해주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
#define INF 987654321
using namespace std;
int t, n, m, w, a, b, c, cycle;
int dist[505];
vector<vector<pair<int, int>>> vt;
int main() {
    scanf("%d", &t);
    while (t--) {
        cycle = false;
        scanf("%d%d%d", &n, &m, &w);
        vt.clear();
        vt.resize(n + 1);
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d", &a, &b, &c);
            vt[a].emplace_back(b, c);
            vt[b].emplace_back(a, c);
        }
        for (int i = 0; i < w; i++) {
            scanf("%d%d%d", &a, &b, &c);
            vt[a].emplace_back(b, -c);
        }
        for (int i = 2; i <= n; i++)
            dist[i] = INF;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                for (auto k : vt[j]) {
                    int there = k.first;
                    int d = k.second;
                    if (dist[j] != INF && (dist[there]>dist[j] + d)) {
                        dist[there] = dist[j] + d;
                        if (i == n)cycle = true;
                    }
                }
            }
        }
        if (cycle)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}