1865. 웜홀

1865. 웜홀

 

 

벨만-포드를 응용한 문제이다.

• 특정 지점에서 다른 지점까지의 최단 거리를 구할 때, 다익스트라를 사용한다.
• 이때 음수 가중치가 존재한다면, 벨만-포드를 사용한다.
  벨만-포드는 음수 사이클을 확인할 때도 사용한다.
• 모든 지점 간의 최단 거리를 구할 때는 플로이드-워셜을 사용한다.
• 그 외에, 최소 신장 트리(MST)를 구할 때는 크루스칼을 사용한다.

 

이 문제는 벨만-포드 알고리즘을 수행해 1번부터 다른 지점까지의 최단 거리를 구한 후, 마지막 N번째에서 음수 사이클을 확인하는 문제다.

• 음수 사이클을 판별하는 것이 중점이므로, 몇 번을 출발지로 할 지는 중요하지 않다.

 

단, 1번에서 도달 불가능한 부분에 음수 사이클이 존재할 수도 있으므로, 이 문제에선 ∞를 확인하는 부분을 없애줘야 한다.

 

#include <iostream>
#include <vector>

#define UNREACHABLE 1000

using namespace std;

struct Edge
{
    int start;
    int end;
    int time;
};

int main(int argc, char* argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int TC;
    cin >> TC;

    while (TC--)
    {
        int N, M, W;
        cin >> N >> M >> W;

        vector<Edge> edges;

        for (int i = 0; i < M; ++i)
        {
            int start, end, time;
            cin >> start >> end >> time;

            edges.push_back({start, end, time});
            edges.push_back({end, start, time});
        }

        for (int i = 0; i < W; ++i)
        {
            int start, end, time;
            cin >> start >> end >> time;

            edges.push_back({start, end, -time});
        }

        vector<int> cost(N + 1, UNREACHABLE);
        
        while (--N)
        {
            for (Edge& edge : edges)
            {
                int cst = cost[edge.start] + edge.time;

                if (cst < cost[edge.end])
                    cost[edge.end] = cst;
            }
        }

        bool bNegativeCycle = false;

        for (Edge& edge : edges)
        {
            int cst = cost[edge.start] + edge.time;

            if (cst < cost[edge.end])
            {
                bNegativeCycle = true;
                break;
            }
        }

        cout << (bNegativeCycle ? "YES\n" : "NO\n");
    }

    return 0;
}