BOJ - 1865 웜홀

웜홀을 거쳐 시작지점으로 돌아왔을 때 시간이 뒤로 갔는지 판단하는 문제이다.

문제풀이 전략
시작지점이 주어지지 않았기 때문에 모든 점에서 모든 점까지의 경로를 구한 후 마지막에 자기 자신까지의 구해진 경로가 음수인지 판단하면 된다.

위 과정을 플로이드 워셜을 사용하여 풀이하였다.

코드

#include<iostream>
#include<vector>

#define INF 25000001
using namespace std;

int n,m,w;
int dis[501][501];
int main(){
    int tc;
    cin >> tc;
    for(int i=0;i<tc;i++){
        cin >> n >> m >> w;

        for(int a=1;a<=n;a++){
            for(int b=1;b<=n;b++){
                dis[a][b] = INF;
            }
        }

        for(int j=0;j<m;j++){
            int s,e,t;
            cin >> s >> e >> t;
            dis[s][e] = min(dis[s][e],t);
            dis[e][s] = min(dis[e][s],t);
        }
        for(int j=0;j<w;j++){
            int s,e,t;
            cin >> s >> e >> t;
            dis[s][e] = min(dis[s][e], -t);
        }

        for(int s=1;s<n+1;s++){
            for(int e=1;e<n+1;e++){
                for(int mid=1;mid<n+1;mid++){
                    int cur = dis[s][mid] + dis[mid][e];
                    if(dis[s][e] < cur)
                        continue;
                    dis[s][e] = cur;
                }
            }
        }

        int flag = 0;
        for(int a=1;a<n+1;a++){
            if(dis[a][a] < 0) {
                flag = 1;
                break;
            }
        }

        if(flag == 0)
            cout << "NO\n";
        else
            cout << "YES\n";
    }
}

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

더 알아볼 점
모든 점이 아닌 한 점에서만 판단을 해도 문제를 해결할 수 있다고 한다.

즉, 모든 점에서 모든 경로를 구한 플로이드 워셜이 아닌 한 점에서 다른 점까지의 거리를 구하는 벨만포드 알고리즘을 통하여 구할 수 있다는 것이다.
(다익스트라는 음의 간선은 불가)

이 방법을 좀 더 알아봐야겠다.