백준 1865 웜홀 쉬운 풀이 (C++/CPP)

문제링크 : https://www.acmicpc.net/problem/1865

문제 추상화

• 음의 간선을 통해 사이클이 생기는지 확인하는 문제

아이디어

• 밸만 포트만 사용하여 사이클이 생기는지 확인
• 사이클 확인할경우, 출발점 지정해줄 필요 없음

시간복잡도 계산

• 테스트캐이스 : O(TC)
• 밸만 포드만 : O(NM)
• 총합 : O(TC * N * M) : 5 * 500 * 2500 = 6.25e6 > 가능

인트 계산

• N * M * T의 최대 수 가능
• 500 * 2500 * 1e4 = 1.25e6 * e4 = e10 > long long 사용

코드

#include <iostream>
#include <tuple>
#include <vector>
 
 
using namespace std;
typedef long long ll;
typedef tuple<int, int, int> ti3;
 
const ll inf = 2e10;
ll dist[510];
vector<ti3> edge;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int TC; cin >> TC;
    while(TC--) {
        fill(dist, dist+510, 0);
        
        edge.clear();
        int N,M,W; cin >> N >> M >> W;
        for(int i=0; i<M; i++) {
            int a,b,c; cin >> a >> b >> c;
            edge.push_back({a,b,c});
            edge.push_back({b,a,c});
        }
        
        for(int i=0; i<W; i++) {
            int a,b,c; cin >> a >> b >> c;
            edge.push_back({a,b,-c});
        }
        
        // 모든 간선을 거침
        for(int i=0; i<N-1; i++) {
            for(int j=0; j<edge.size(); j++) {
                int a,b,c; tie(a,b,c) = edge[j];
                
                if(dist[b] > dist[a] + c) dist[b] = dist[a] + c;
            }
        }
        
        bool sw = false;
        for(int j=0; j<edge.size(); j++) {
            int a,b,c; tie(a,b,c) = edge[j];
            
            if(dist[b] > dist[a] + c ) {
                cout << "YES\n";
                sw = 1;
                break;
            }
        }
        
        if(sw == false) cout << "NO\n";
        
    }
    
    return 0;
}
 

문제유형

• 밸만포드 - 사이클 확인
  • 출발점 없이 사이클만 확인
  • dist 배열 시작점을 0으로 만들고 나머지 inf로 만들고 진행할 경우, 시작점 고립되어있을경우 사이클 확인 불가