백준 1865 웜홀 (C++)

1865번: 웜홀

벨만 포드 알고리즘을 이용한 문제이다. 벨만 포드 알고리즘을 통해 음수 사이클이 존재하는지 확인을 하면 된다. 모든 간선을 N-1번 반복하여 방문하면서 최단 거리를 구한 후, 한번 더 방문했을 때 최단 거리가 갱신이 된다면 음수 사이클이 존재한다는 것, 즉 시간이 이전보다 더 되돌아감을 의미하게 되므로 YES를 출력해주고 아니면 NO를 출력해주면 된다. 벨만 포드 알고리즘을 처음 접해보아서 굉장히 많이 해맷다. 여기에 굉장히 친절하게 설명을 해주어서 잘 이해할 수 있었다. 다익스트라, 벨만 포드 그리고 플로이드 워셜과 같은 최단 거리를 찾는 알고리즘에 대해 잘 알아두어야 겠다.

#include <iostream>
#include <vector>
#include <cstring>

#define INF 987654321

using namespace std;

int N, M, W;
int S, E, T;
vector<pair<pair<int, int>, int>> v;
int d[501];

void solution() {
    string result = "NO";

    memset(d, INF, sizeof(d));
    d[1] = 0;

    for (int i = 0; i < N - 1; i++) {
        for (int j = 0; j < v.size(); j++) {
            int s = v[j].first.first;
            int e = v[j].first.second;
            int t = v[j].second;

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

    for (int i = 0; i < v.size(); i++) {
        int s = v[i].first.first;
        int e = v[i].first.second;
        int t = v[i].second;

        if (d[e] > d[s] + t) {
            result = "YES";
            break;
        }
    }

    cout << result << "\n";
}

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

    int TC;
    cin >> TC;

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

        cin >> N >> M >> W;

        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 });
        }

        solution();
    }

    return 0;
}