백준[1865] 웜홀

아이디어

• 밸만포드 알고리즘을 사용할 줄 안다

풀이

1. 밸만 포드 알고리즘 이용, n-1번 각 노드에서 다른 노드로 가는 가중치를 계산한다.
2. 한번 더 가중치를 계산하여, 이번에도 갱신될 경우 음수사이클이 존재한다고 판단, 이는 시간이 돌아가는 것과 같은 말이기에, YES를 출력하고, 없으면 NO를 출력한다

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<pair<int, int>, int>> v;
int dist[501];

void bellmanFord(int n) {
    for (int i = 0; i < n; i++) {
        for (int pos = 0; pos < v.size(); pos++) {
            int from = v[pos].first.first;
            int to = v[pos].first.second;
            int cost = v[pos].second;

            if (dist[from] + cost < dist[to]) dist[to] = dist[from] + cost;
        }
    }

    for (int pos = 0; pos < v.size(); pos++) {
        int from = v[pos].first.first;
        int to = v[pos].first.second;
        int cost = v[pos].second;
        if (dist[from] + cost < dist[to]) {
            cout << "YES\n";
            return;
        }
    }

    cout << "NO\n";

}


int main() {

    int tc; cin >> tc;

    while (tc--) {
        v.clear();
        int n, m, w; cin >> n >> m >> w;
        for (int i = 1; i <= n; i++) dist[i] = 987654321;

        for (int i = 0; i < m; i++) {
            int from, to, cost; cin >> from >> to >> cost;
            v.push_back({ {from,to},cost });
            v.push_back({ {to,from},cost });
        }
        for (int i = 0; i < w; i++) {

            int from, to, cost; cin >> from >> to >> cost;
            v.push_back({ {from,to},-cost });
        }

        bellmanFord(n);
    }


    return 0;
}

평가

이 문제는 벨만포드 알고리즘을 알고 있다면 접근 할 수 있는 문제입니다.
하지만 이 문제의 함정이 2가지 있습니다.

1. 도로는 무방향 간선이지만 웜홀은 유방향 간선이다
도로와 웜홀은 다른 경우입니다. 도로의 경우에는 무방향 간선이기에, from->to , to->from 모든 경우를 다 기록해주셔야합니다.

2. 기존 벨만포드 알고리즘의 if(dist[INF] == continue),
즉 갱신이 안된 노드에 대한 계산을 배제하는 코드를 오히려 제거해야한다.
보통 벨만포드 알고리즘의 경우, 한 노드에서 다른 노드로 가는 최단거리를 구하기 위하기 위해서 dist[0] = 1 등 임의의 노드를 0으로 초기화 할 것입니다.
하지만, 이 문제에서는 그렇게 하시면 안됩니다. 왜냐하면 모든 그래프가 연결되어 있다는 조건이 없고, 꼭 0에서 시작해야 한다는 말이 없기 때문입니다.

예를 들어,
1 -> 2 -> 1
3 -> 4 -> 3
2가지의 그래프가 있다고 생각하면, 3->4->3 의 그래프가 음수 사이클이 존재한다고 해도, 우리는 1의 노드부터 조사를 할 것이기 때문에, 1번-2번노드 둘다 3번-4번 노드로 갈 수 없으므로(dist 가 INF일 것이기 때문), 음수사이클이 없다고 판단, NO를 출력해 버리게 됩니다.
따라서 이를 주의해서 풀이를 해주셔야합니다.