[백준] 1865 : 웜홀

www.acmicpc.net/problem/1865

1865번: 웜홀

---

• 처음엔 플로이드-와샬 문제인 줄
• 문제 태그에 벨만-포드라고 되어 있는데, 풀어본 적 없어서 먼저 벨만포드를 공부하고 풀었다.
• 처음엔 거리 갱신 시 시작점이 INF 일 경우 갱신하지 않는 것으로 코드를 작성했다가, 계속 틀렸었다.
• 이는 특정 노드에서 시작할 경우 해당 노드가 다른 음의 순환이 있는 노드들과 단절돼있을 경우 반영이 안되기 때문이다.
• 사실 음의 순환이 존재하는지만 확인하기 위해서는 INF 비교나 INF 초기화가 필요 없다.
• 어차피 n-1 번 동안 최단거리로 업데이트 되고, 마지막 반복에서 갱신이 일어나는지만 확인하면 되기 때문.

---

#include <iostream>
#include <vector>

#define INF 100000000

using namespace std;

int TC;
int N, M, W;

bool bf()       // 음의 싸이클 존재 여부 리턴
{
    cin >> N >> M >> W;
    vector<pair<pair<int,int>,int>> edges;      // 입력받는 모든 엣지들 저장
    int s, e, t;
    for(int m = 0 ; m < M ; m++)
    {
        cin >> s >> e >> t;
        edges.push_back({{s,e},t});             // 양방향으로 저장
        edges.push_back({{e,s},t});
    }
    for(int w = 0 ; w < W ; w++)
    {
        cin >> s >> e >> t;
        edges.push_back({{s,e},-t});
    }
    vector<int> dist(N+1, INF);                 // 거리 정보, 대충 초기화
    dist[1] = 0;                                // 시작점은 아무데나 설정
    for(int v = 0 ; v < N ; v++)                // n-1 번 반복으로 최단거리 구하고, 마지막 1번으로 변화 유무 파악
    {
        for(int i = 0 ; i < edges.size() ; i++) // 모든 엣지를 보면서
        {
            int start = edges[i].first.first, end = edges[i].first.second;
            if((dist[end] > dist[start] + edges[i].second))         // 거리 갱신되는 노드들 업데이트
            {
                if(v == N-1) return true;                           // 마지막 반복이었을 경우, 거리 갱신 시 음의 싸이클 존재
                dist[end] = dist[start] + edges[i].second;
            }
        }
    }
    return false;
}

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

    cin >> TC;
    for(int tc = 0 ; tc < TC ; tc++)
    {
        if(bf()) cout << "YES" << endl;     // 음의 싸이클이 존재할 경우에 따라 답 출력
        else cout << "NO" << endl;
    }
}