BOJ #1865 웜홀

문제 링크 : https://www.acmicpc.net/problem/1865

1865번: 웜홀

 

그래프의 경로 상에 음수 간선이 존재하는 벨만포드 알고리즘 입문 문제입니다.

 

별도의 트릭을 필요로 하지 않으며 벨만포드 알고리즘을 충실히 구현하면 됩니다.

 

벨만포드 알고리즘의 정의상, 정점의 개수(V) - 1회만큼 경로 갱신을 반복하면 전체 최단 경로들을 모두 구할 수 있습니다.

 

이후에 한번 더 인접 리스트를 통해 경로 갱신을 했을 때 최단 거리가 갱신되는 경우가 발생한다면,

 

해당 그래프는 무한히 최단 경로가 갱신되는 음의 cycle이 존재한다는 것을 알 수 있습니다.

 

cnt :: 최단 경로 갱신을 반복하는 횟수

updated :: V번째로 경로를 갱신할 때, 경로가 갱신된다면 음의 cycle이 존재

 

#include <bits/stdc++.h>
using namespace std;
 
int t, n, m, w, dist[501];
vector <pair<int, int>> vc[501];
 
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d", &n, &m, &w);
        for (int i = 1; i <= n; i++)
            dist[i] = 1e9, vc[i].clear();
        int a, b, c;
        for (int i = 1; i <= m; i++) {
            scanf("%d%d%d", &a, &b, &c);
            vc[a].push_back({ b, c });
            vc[b].push_back({ a, c });
        }
        for (int i = 1; i <= w; i++) {
            scanf("%d%d%d", &a, &b, &c);
            vc[a].push_back({ b, -c });
        }
        dist[1] = 0;
        bool updated = true;
        int cnt = 0;
        while (updated && cnt != n) {
            updated = false;
            cnt++;
            for (int i = 1; i <= n; i++) {
                for (auto x : vc[i]) {
                    if (dist[x.first] > dist[i] + x.second) {
                        dist[x.first] = dist[i] + x.second;
                        updated = true;
                    }
                }
            }
        }
        if (cnt == n)
            printf("YES\n");
        else
            printf("NO\n");
    }
}