[BOJ 백준] 1865번 웜홀

문제

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

1865번: 웜홀

접근

 문제에서 웜홀은 결국 음의 값을 가지는 간선이기 때문에 벨만-포드(Bellman-Ford)알고리즘을 사용하여 문제를 해결하였다. 

코드

#include <iostream>
#include <vector>

#define endl "\n"
#define MAX 30000000

using namespace std;

struct eg {
    int s, e, t;
};

int n, m, w;
bool chk(vector<eg> v) {
    vector<int> dist(n + 1, MAX);

    int s, e, t;
    dist[1] = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < v.size(); j++) {
            s = v[j].s;
            e = v[j].e;
            t = v[j].t;
            if (dist[e] > dist[s] + t)
                dist[e] = dist[s] + t;
        }
    }
    for (int j = 0; j < v.size(); j++) {
        s = v[j].s;
        e = v[j].e;
        t = v[j].t;
        if (dist[e] > dist[s] + t)
            return true;
    }

    return false;
}

int main() {
    int tc;
    cin >> tc;
    for (int i = 0; i < tc; i++) {
        cin >> n >> m >> w;
        int s, e, t;
        vector<eg> v;
        for (int j = 0; j < m; j++) {
            cin >> s >> e >> t;
            v.push_back({s, e, t});
            v.push_back({e, s, t});
        }
        for (int j = 0; j < w; j++) {
            cin >> s >> e >> t;
            v.push_back({s, e, -t});
        }
        if (chk(v))
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study