(C++) - 백준(BOJ) 1865번 : 웜홀

www.acmicpc.net/problem/1865

1865번: 웜홀

벨만포드 문제였습니다.

 

풀이방법

 모든 정점을 확인하면서 갱신이 되었다면 flag를 세워주고 갱신이 되지 않았다면 다시 돌아올 수 없는 경우므로 flag를 내려주는 방식으로 벨만포드 알고리즘으로 순회하며 정답을 찾습니다.

 

Code

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
using pii = pair<int,int>;
int tc;
int n, m, w;

vector <pii> graph[501];

bool bellmanFord(int start,int end){
    vector<int> dist(end+1,INF);
    dist[start] = 0;
    int flag = 0;
    for(int i = 1; i <= end; i++){
        flag = 0;
        for(int cur = 1; cur <= end; cur++){
            for(auto &el : graph[cur]){
                int next = el.first;
                int nextCost =el.second;
                if(dist[next] > dist[cur] + nextCost){
                    dist[next] = dist[cur] + nextCost;
                    flag = true;
                }
            }
        }
        if(!flag) return false;
    }
    return true;
}

int main(){
    cin >> tc;
    while(tc--){
        cin >> n >> m >> w;
        for(int i = 0; i <= 500; i++) graph[i].clear();
        for(int i = 0,s,e,t; i < m; i++){
            cin >> s >> e >> t;
            graph[s].push_back({e,t});
            graph[e].push_back({s,t});
        }
        for(int i = 0,s,e,t; i < w; i++){
            cin >> s >> e >> t;
            graph[s].push_back({e,-t});
        }
        if(bellmanFord(1,n)) cout << "YES\n";
        else cout << "NO\n";
    }
}