BOJ 1865 - 웜홀

문제

\(N\)개의 정점에 대한 \(M\)개의 가중치가 양수인 양방향 간선과, \(W\)개의 가중치가 음수인 단방향 간선이 주어진다.
이때 음수 사이클이 존재하는지 판별하는 문제이다.

\(1\le N \le 500,\; 1\le M \le 2500,\; 1\le W \le 200\)이다.
간선의 가중치 \(T_i\)에 대해 \(-10000 \le T_i \le 10000\)이다.

풀이

동일한 경로인 음수 간선이 존재할 경우 양수 간선은 사용하지 않기 때문에 한 번에 인접 배열에 입력받은 후 간선 리스트를 만들 수 있다.
벨만 포드 알고리즘을 사용하여 음수 사이클의 존재 여부를 판별할 수 있다.

소스코드

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

using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using lld = long long;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tc, n, m, w, s, e, t;
    cin >> tc;
    vector<string> ans;
    while (tc--) {
        cin >> n >> m >> w;
        vi sp(n, 99999);
        vector<vi> adje, adjv(n, vi(n, 99999));
        for (int i = 0; i < m; i++) {
            cin >> s >> e >> t;
            s--, e--;
            if (adjv[s][e] > t) adjv[s][e] = t;
            if (adjv[e][s] > t) adjv[e][s] = t;
        }
        for (int i = 0; i < w; i++) {
            cin >> s >> e >> t;
            s--, e--;
            if (adjv[s][e] > -t) adjv[s][e] = -t;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (adjv[i][j] != 99999) {
                    vi tv;
                    tv.push_back(i);
                    tv.push_back(j);
                    tv.push_back(adjv[i][j]);
                    adje.push_back(tv);
                }
            }
        }
        sp[0] = 0;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < adje.size(); j++) {
                int curs = adje[j][0], cure = adje[j][1], w = adje[j][2];
                if (sp[cure] > sp[curs] + w) sp[cure] = sp[curs] + w;
            }
        }
        n = 1;
        for (int i = 0; i < adje.size(); i++) {
            int curs = adje[i][0], cure = adje[i][1], w = adje[i][2];
            if (sp[cure] > sp[curs] + w) {
                ans.push_back("YES");
                n = 0;
                break;
            }
        }
        if (n) ans.push_back("NO");
    }
    for (int i = 0; i < ans.size() - 1; i++)
        cout << ans[i] << '\n';
    cout << ans.back();
    return 0;
}

풀고나서

• 다익스트라로 해결하려 하다가, 음수 간선이 2개 이상 포함된 음수 사이클을 해결하는 과정에서 막혀 벨만 포드를 사용했다.
  • 음수 사이클의 음수 간선이 1개라고 보장되는 경우, 음수 간선의 시작점과 끝점에 대해 음수 간선을 제외한 나머지 간선들을 사용하여 최소 경로를 구한 후 음수 가중치와 비교하면 음수 사이클을 판별 가능하다.