[C++] 웜홀 (백준 1865번)

https://www.acmicpc.net/problem/1865

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int tc;
    cin >> tc;

    while (tc--) {
        int n, m, w;
        cin >> n >> m >> w;
        vector<vector<int>> edge;
        vector<int> dst(n + 1, 100000000);

        int s, e, t;
        dst[1] = 0;

        for (int i = 0; i < m; i++) {
            cin >> s >> e >> t;
            edge.push_back({s, e, t});
            edge.push_back({e, s, t});
        }

        for (int i = 0; i < w; i++) {
            cin >> s >> e >> t;
            edge.push_back({s, e, -t});
        }

        int es = edge.size();
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < es; j++) {
                s = edge[j][0];
                e = edge[j][1];
                t = edge[j][2];
                if (dst[e] > dst[s] + t) {
                    dst[e] = dst[s] + t;
                }
            }
        }

        bool infinite = false;
        for (int i = 0; i < es; i++) {
	    	s = edge[i][0];
	    	e = edge[i][1];
	    	t = edge[i][2];
	    	if (dst[e] > dst[s] + t) {
	    		infinite = true;
                break;
	    	}
	    }

        if (infinite) cout << "YES\n";
        else cout << "NO\n";
    }
}

음의 간선이 있는 경우이기 때문에 다익스트라 알고리즘이 아닌 벨만–포드 알고리즘을 사용해야 한다. 벨만–포드 알고리즘은 음의 간선이 있을 경우 최단 경로를 찾을 때에도 사용되지만, 음수 사이클의 존재를 탐지하는 데에 더 많이 사용된다. 음수 사이클이 있다는 것은 무제한으로 시간을 줄일 수 있다는 것을 의미하고, 이 문제 역시 음수 사이클이 있는지 체크하면 되는 것이다. (AC)

벨만-포드 알고리즘의 동작 과정

1. 출발 노드 설정: 시작할 노드를 정함.
2. 최단 거리 테이블 초기화: 시작 노드를 제외한 모든 노드의 거리를 무한대로 설정함.
3. V - 1회 반복:
모든 간선에 대해 현재의 최단 거리를 기준으로 거리 테이블을 업데이트함.
각 간선 (u, v)를 확인하며, 거리[u] + 가중치 < 거리[v]일 때, 거리[v]를 거리[u] + 가중치로 갱신함.
4. 음수 사이클 감지 (옵션):
3번 과정을 한 번 더 수행하여 갱신이 발생하면 음수 사이클이 존재하는 것임.

벨만-포드 알고리즘의 특징

• 음수 가중치 허용: 음수 가중치를 가지는 간선이 포함된 그래프에서도 최단 경로를 찾을 수 있음.
• 음수 사이클 감지: 음수 사이클이 존재하는 경우 이를 감지할 수 있음.
• 시간복잡도: O(V*E)로 다익스트라 알고리즘보다 느리지만, 음수 가중치가 있는 그래프에 적합함.