Wormhole 1865번 [백준]

이번 문제는 최단거리를 구하는 문제였습니다. 처음에 다익스트라로 풀 수 있는 줄 알고 씨름을 했었는데, 알고 보니 벨만 포드 알고리즘(Bellman-Ford)을 사용하는 것이 더 군요.

이번 문제를 풀면서 최단 거리를 구할 때, 가중치중에 음수인 EDGE가 존재하는 네트워크에서는 다익스트라가 허용이 안된다는 것을 알았습니다.

문제에서는, 다시 되돌아 왔을 때, 0 혹은 음수인 값이 나오는 경우 YES 아닌 경우 NO을 출력하라고 하였습니다.

근데 0 혹은 음수가 나온다는 것은 문제안에 음수 값을 갖는 CYCLE이 존재한다는 것이고, 벤담 포드 알고리즘으로는 CYCLE이 있는 경우는 계산하지 못합니다.

따라서 본래 i을 N-1번 루프 시키는것과 달리, N번 루프를 시켜, 음수 값을 갖는 CYCLE이 있는지를 확인할 수 있었습니다.

#import<bits/stdc++.h>

using namespace std;
#define endl '\n'
#define fast_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i, j) for(int i=0;i<j;i++)
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
#define YES "YES"
#define NO "NO"

const int MAXN = 510;
const int INF = 987654321;

int n,m,w;
int Dist[MAXN];
void Init(){
    for(int i =0;i<MAXN;i++)Dist[i] = INF;
}
void Shortest_Path(vector<pii> *v){
    bool cycle = false;
    rep(i,n){//cycle n
        rep(j,n){
            rep(k,v[j].size()){//adjacnet node
                int next = v[j][k].ff,d = v[j][k].ss;
                if(v[j][k].ss == INF)continue;
                else if(Dist[next] > Dist[j] + d){
                    Dist[next] = Dist[j] +d;
                    if(i == n-1)cycle = true;
                }
            }
        }
    }
    if(cycle)cout<<YES<<endl;
    else cout<<NO<<endl;
}
void solve(){
    rep(i,MAXN)Dist[i] = INF;
    int i =0;
    cin>>n>>m>>w;
    int start,end,t;
    vector<pii> v[n];
    rep(i,m){
        cin>>start>>end>>t;
        v[start-1].pb({end-1,t});
        v[end-1].pb({start-1,t});
    }rep(i,w){
        cin>>start>>end>>t;
        v[start-1].pb({end-1,-t});
    }
    Shortest_Path(v);
}
int main() {
    fast_io;
    int t;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

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