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

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

1865번: 웜홀

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

struct Info
{
    int s, e, t;
};

int N, M, W;
int dist[501];

vector<Info>v;

void Bellman_Ford()
{
    for(int i=1; i<N; i++)   //N-1까지만 탐색
    {
        for(int j=0; j<v.size(); j++)
        {
            int s = v[j].s;
            int e = v[j].e;
            int t = v[j].t;

            if(dist[e] > dist[s] + t)
            {
                dist[e] = dist[s] + t;
            }
        }
    }

    for(int i=0; i<v.size(); i++)
    {
        int s = v[i].s;
        int e = v[i].e;
        int t = v[i].t;
        if(dist[e] > dist[s] + t) //갱신 -> 음수사이클 존재
        {
            cout << "YES" <<"\n";
            return;
        }
    }
    cout << "NO" <<"\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T; 
    cin >> T;

    while(T--)
    {
        v.clear();

        cin >> N >> M >> W;

        for (int i = 1; i <= N; i++) 
        {
            dist[i] = MAX;
        }

        int S, E, T;

        for(int i=0; i<M; i++)
        {
            cin >> S >> E >> T; //무방향
            v.push_back({S, E, T});
            v.push_back({E, S, T});
        }

        for(int i=0; i<W; i++)
        {
            cin >> S >> E >> T; //유방향
            v.push_back({S, E, -T});  //웜홀은 음의 가중치
        }

        Bellman_Ford();
    }    

    return 0;

}

밸만 포드 알고리즘 문제이다.

원래 시작점을 정하고 하는데, 해당 문제에서는 음의 사이클이 존재하는 유무만 파악하면 되기에 굳이 시작점을 정해주지 않아도 된다.

 

도로는 무방향이고, 웜홀은 유방향이다.

이때 웜홀은 돌아오는 것이기에 때문에 가중치를 음의 가중치로 해야한다.

 

N-1번까지 각 정점에 대한 거리를 탐색을 돌리고 난 후에 마지막으로 탐색을 한 번만 더 돌린다.

이때 최소 비용이 변하는 정점이 있다면 이는 음의 사이클이 존재하는 것이다.

음의 사이클이 없는 그래프는 이후 탐색을 하더라도 최소 비용이 변하는 정점이 생기지 않는다.