1865번

1865번 - 웜홀

11657 타임머신과 같이, 음수 간선이 있는 그래프에서 최단 거리를 구하는 벨만 포드 알고리즘을 쓰면 된다.

근데 웜홀 문제는 음수 싸이클이 존재하는지 여부만 확인하면 된다.

음수 싸이클이 존재하면, 충분히 음수 싸이클을 돈 뒤에 양수 간선을 이동해서 시작점으로 이동하면, 항상 시작점에서 출발할 때보다

더 이른 시간에 도착하기 때문이다.

<정답 코드> 

#include<iostream>
#include<vector>
using namespace std;
 
const int INF = 987564321;
int n, m, w;
 
bool bellman_ford(int start,vector<vector<pair<int,int>>> &v,vector<int> &upper)
{
    for (int iter = 1; iter <= n; iter++)
    {
        bool update = false;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j < v[i].size(); j++)
            {
                int next = v[i][j].first;
                int cost = v[i][j].second;
 
                if (upper[i] != INF && upper[i] + cost < upper[next])
                {
                    upper[next]=upper[i] + cost;
                    update = true;
                }
            }
        }
 
        if (iter == n && update)
        {
            return false;
        }
    }
 
    return true;
 
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
    while (tc--)
    {
        scanf("%d %d %d", &n, &m, &w);
 
        vector<vector<pair<int, int>>> v(n + 1);
        vector<int> upper(n + 1);
 
        for (int i = 1; i <= n; i++)
        {
            upper[i] = INF;
        }
 
        for (int i = 0; i < m; i++)
        {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            v[a].push_back(make_pair(b, c));
            v[b].push_back(make_pair(a, c));
        }
 
        for (int i = 0; i < w; i++)
        {
            int a, b, c;
            scanf("%d %d %d", &a,&b, &c);
            v[a].push_back(make_pair(b, -c));
        }
 
        int start = 1;
        upper[start] = 0;
        if (!bellman_ford(start, v, upper))
        {
            printf("YES\n");
        }
        else
        {
            printf("NO\n");
        }
 
    }
 
    return 0;
}