BOJ 1865 - 웜홀

핵심 아이디어

이 문제는 음수 사이클 존재 여부를 판별하는 문제다.

• 일반 도로: 양방향, 양수 가중치 (시간 증가)
• 웜홀: 단방향, 음수 가중치 (시간 감소)

출발점으로 돌아왔을 때 시간이 줄어드는 경우 = 음수 사이클 존재 → YES

---

알고리즘 선택: 벨만-포드

| 알고리즘 | 출발점 | 음수 간선 | 시간복잡도 | |---|---|---|---| | 다익스트라 | 단일 출발 | ❌ 불가 | O((V+E) log V) | | 벨만-포드 | 단일 출발 | ✅ 가능 | O(VE) | | 플로이드-워셜 | 모든 쌍 | ✅ 가능 | O(V³) |

음수 간선이 존재하므로 다익스트라 불가 → 벨만-포드 사용

---

벨만-포드 원리

Relaxation: 모든 간선에 대해 거리 갱신을 반복

dist[도착] > dist[출발] + 비용 이면 갱신

핵심: 노드가 N개일 때 최단경로는 최대 N-1개의 간선을 거친다 → relaxation을 N-1번 반복하면 모든 최단거리 확정

음수 사이클 탐지: N-1번 반복 후 한 번 더 순회했을 때 갱신이 일어나면 음수 사이클 존재 → 이미 확정됐어야 할 거리가 줄어든다는 것 = 무한히 줄어드는 사이클 존재

---

주요 포인트

1. 시작점을 따로 두지 않는다

그래프가 여러 연결 요소로 나뉠 수 있어서, 특정 시작점(예: 1번 노드)에서 출발하면 닿지 않는 연결 요소의 음수 사이클을 탐지하지 못한다.

모든 노드의 distance를 INF로 초기화하면 어느 연결 요소에 있든 음수 사이클이 있으면 탐지 가능하다.

대신 이 방식은 "특정 출발점에서의 최단거리"가 아니라 음수 사이클 존재 여부만 판별할 때만 유효하다.

2. 도로는 양방향, 웜홀은 단방향

// 도로: 양방향
edges.push_back({S, E, T});
edges.push_back({E, S, T});

// 웜홀: 단방향, 음수
edges.push_back({S, E, -T});

3. 간선 리스트 구조

벨만-포드는 "모든 간선을 순회"하는 게 핵심이라 인접 행렬보다 간선 리스트가 자연스럽다. tuple<int,int,int>으로 {출발, 도착, 비용} 저장.

---

최종 코드

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int TC;
    const int INF = 1e9;
    cin >> TC;
    while(TC--){
        int N, M, W;
        cin >> N >> M >> W;
        vector<int> distance(N+1, INF);
        vector<tuple<int, int, int>> edges;
        for(int i = 0; i < M; i++){
            int S, E, T;
            cin >> S >> E >> T;
            edges.push_back({S, E, T});
            edges.push_back({E, S, T});
        }
        for(int i = 0; i < W; i++){
            int S, E, T;
            cin >> S >> E >> T;
            edges.push_back({S, E, -T});
        }
        
        for(int i = 0; i < N-1; i++){
            for(const auto &edge : edges){
                auto [S, E, T] = edge;
                if(distance[E] > distance[S] + T){
                    distance[E] = distance[S] + T;
                }
            }
        }
        bool hasNegativeCycle = false;
        for(const auto &edge : edges){
            auto [S, E, T] = edge;
            if(distance[E] > distance[S] + T){
                hasNegativeCycle = true;
            }
        }
        if(hasNegativeCycle) cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
    return 0;
}