백준 #1865 웜홀

BOJ #1865 - 웜홀

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

# 문제 분류

최단 경로 알고리즘 (벨만 포드)

풀이 접근 방법

벨만 포드에서 INF 비교를 안 해야한다 ...

벨만 포드 알고리즘에서 INF 비교를 하지 않아야 AC가 나오는 이유는 뭘까 https://www.acmicpc.net/board/view/50494

답변은 이거였습니다. INF의 값을 설정하는 이유는 단절이 되었다를 표시하고, 어떤 지점으로 부터의 거리를 구하려고 할 때 쓰입니다. 왜냐면 단절된 경우에는 갈 수 없거든요.

따라서 만약 단순 그래프에서의 사이클 유무만 파악할 때는 dist[]초기화를 어떤 값으로 해주어도 상관이 없어요. 왜냐면 거리를 구하는 게 아니라 마지막에서 음의 사이클이 존재할 때, 변화만 파악하는 것이니깐요.

그래서 dist[]를 memset -1로 초기화 한 코드도 잘 통과했고요. 답변이 되었으면 좋겠습니다.

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

#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define fup(i, a, b, c) for (int(i) = (a); (i) <= (b); (i) += (c))
#define fdn(i, a, b, c) for (int(i) = (a); (i) >= (b); (i) -= (c))
#define endl "\n"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const ll MOD = 1e9 + 7;
const int stMAX = 1 << 18;
const int INF = 1e9;
int N, M, W, T, S, E, TC;

const int MAX_D = 3000;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> TC;

    fup(_, 1, TC, 1) {
        vii adj[3000];

        cin >> N >> M >> W;

        fup(i, 1, M, 1) {
            cin >> S >> E >> T;

            adj[S - 1].pb({E - 1, T});
            adj[E - 1].pb({S - 1, T});
        }

        fup(i, 1, W, 1) {
            cin >> S >> E >> T;

            adj[S - 1].pb({E - 1, -T});
        }

        // 모든 정점에 대해서 벨만 포드를 돌린다.
        bool visited[600] = {false};
        bool flag = false;
        fup(k, 0, N - 1, 1) {
            if (visited[k])
                continue;

            int dist[MAX_D];
            fill(dist, dist + MAX_D, INF);

            dist[k] = 0;
            visited[k] = 1;
            int a = 0;
            while (true) {
                if (a == N)
                    break;
                fup(j, 0, N - 1, 1) {
                    for (auto &p : adj[j]) {
                        int next = p.first, cost = p.second;
                        visited[next] = 1;
                        if (dist[j] != INF && dist[next] > dist[j] + cost) {
                            dist[next] = dist[j] + cost;
                            if (a == N - 1)
                                flag = true;
                        }
                    }
                }
                a++;
            }
        }

        cout << (flag ? "YES" : "NO") << endl;
    }
}