[벨만 포드] BOJ 1865 웜홀

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

1865번: 웜홀

 

문제 해결 알고리즘

 

벨만 포드 알고리즘

 

음의 사이클의 존재 여부를 판단하는 문제.

 

출발점이 어디든 음의 사이클 존재만 판단하면 되므로 한 번만 벨만 포드 알고리즘을 돌리면 된다.

(굳이 모든 출발점에서 음의 사이클 존재 여부 판단할 필요 X, 시간 초과남)

 

if(d[cur_node] != INF && d[next_node] > d[cur_node] + cost)

 

보통의 벨만 포드 알고리즘은 위의 코드처럼 INF값과 비교해서 값을 변경해준다.

 

하지만 이 문제에서는 

 

1
2 0 1
2 2 1

 

위의 테스트 케이스에서 "NO"를 출력할 것이기 때문에 INF값과 비교해주지 않는다.

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

const int INF = 2100000000;
int N, M, W;
vector<tuple<int, int, int>> edges;
int d[501];

bool bf(int start){

    d[start] = 0;

    for(int i=0;i<N;i++){
        for(int j=0;j<edges.size();j++){

            int cur_node = get<0>(edges[j]);
            int next_node = get<1>(edges[j]);
            int cost = get<2>(edges[j]);

            if(d[next_node] > d[cur_node] + cost){
                d[next_node] = d[cur_node] + cost;

                if(i == N-1) return true;
            }
        }
    }

    return false;
}

int main(){

    ios::sync_with_stdio(0);
	cin.tie(0);
    int TC; cin >> TC;

    while(TC--){
        
        cin >> N >> M >> W;

        for(int i=1;i<=N;i++) d[i] = INF;

        int S, E, T;
        for(int i=0;i<M;i++){
            cin >> S >> E >> T;

            edges.push_back({S, E, T});
            edges.push_back({E, S, T});
        }

        for(int i=0;i<W;i++){
            cin >> S >> E >> T;

            edges.push_back({S, E, -T});
        }

        if(bf(1)) cout << "YES\n";
        else cout << "NO\n";
        

        edges.clear();

    }
}