[1865번] 웜홀

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 벨만 포드 :: http://www.crocus.co.kr/search/%EB%B2%A8%EB%A7%8C%20%ED%8F%AC%EB%93%9C

벨만 포드 알고리즘을 지금까지 너무 어렵게 배운 것 같아 다시 배워야 할 것 같다.

이 문제는 그냥 벨만포드 알고리즘을 이용하면 되고, 사이클이 존재한다면 YES, 사이클이 존재하지 않는다면 NO를 출력하면 된다.

이때 사이클이 존재한다는 조건은 cnt == V인데 

벨만포드 알고리즘 정의 상 총 라운드는 V-1번만 돌면 모든 최단 경로를 확인할 수 있다.

하지만 V - 1번 이후 V번째에도 최단 경로가 발견되었다면 그것은 음의 사이클이 존재한다는 의미이다.

소스 코드 : 

#include <cstdio>
#include <vector>
#include <limits.h>
#include <memory.h>
 
#define INF 987654321
 
using namespace std;
 
typedef pair<int, int> pii;
 
 
int main()
{
    int dist[505];
    int tCase;
 
    scanf("%d", &tCase);
 
    while (tCase--)
    {
        int V, E, Hole;
        int cnt = 0;
        vector<pii> adj[505];
 
        scanf("%d %d %d", &V, &E, &Hole);
 
        for (int i = 0; i < E; i++)
        {
            int from, to, val;
            scanf("%d %d %d", &from, &to, &val);
 
            adj[from].push_back(make_pair(to, val));
            adj[to].push_back(make_pair(from, val));
        }
 
        for (int i = 0; i < Hole; i++)
        {
            int from, to, val;
            scanf("%d %d %d", &from, &to, &val);
 
            adj[from].push_back(make_pair(to, -val));
        }
 
        for (int i = 0; i <= V; i++)
            dist[i] = INF;
 
        bool update = true;
        dist[1] = 0;
 
        while (update && cnt != V)
        {
            update = false;
            cnt++;
            for (int i = 1; i <= V; i++)
            {
                for (auto j : adj[i])
                {
                    if (dist[i] + j.second < dist[j.first])
                    {
                        dist[j.first] = dist[i] + j.second;
                        update = true;
                    }
                }
            }
        }
 
        cnt == V ? printf("YES\n") : printf("NO\n");
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>