UVA 00558 - Wormholes

解題觀念

SPFA

可以參考我的課程簡報：MST & Shortest Path
關於 SPFA 的基本觀念可以參考我的這篇文章：Algorithm - SPFA

題目敘述

蟲洞
人們發現了蟲洞，在此題中蟲洞有以下特性：
蟲洞只能是單向的、每個蟲洞可能有多個端點開口
蟲洞的端點開口中有一定的時間差，可以穿越到未來、可以穿越回過去

今有科學家想要穿越回宇宙的起點，故他想利用蟲洞的特性，利用循環多次旅行，來盡可能回到遙遠的過去 (也就是問你有沒有負環存在)

請判斷是否有這樣的蟲洞循環存在

Input

第一行有一整數 t，表示有多少筆測資

每組測資第一行有二整數 N、M
代表有 N 個蟲洞(點)、M 條邊
接下來有 M 行，每行有三個數字 u、v、w
表示蟲洞兩端連接的點及可穿越時間

(為正表示往未來、為負表示往過去)

2
3 3
0 1 1000
1 2 15
2 1 -42
4 4
0 1 10
1 2 20
2 3 30
3 0 -60

Output

若有負環時輸出 possible
無負環則輸出 not possible

possible
not possible

Solution Code

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

const int maxn = 2000+5;
const int INF = 0x3f3f3f3f;

struct Edge{
    int v;
    int w;
};

int N, M;
vector<Edge> G[maxn];

bool SPFA(int S){
    int cnt[maxn]; // 記錄此點被更新過幾次
    int dist[maxn];

    bool inqueue[maxn];
    queue<int> q;

    memset(cnt, 0, sizeof(cnt));
    memset(dist, INF, sizeof(dist));
    memset(inqueue, false, sizeof(inqueue));

    // 推入起點
    q.push(S);
    dist[S] = 0;
    inqueue[S] = true;
    cnt[S] = 1;

    while(!q.empty()){
        int now = q.front();
        q.pop();
        inqueue[now] = false;

        for(auto &e : G[now]){
            if(dist[e.v] > dist[now] + e.w){
                dist[e.v] = dist[now] + e.w;

                if(!inqueue[e.v]){
                    // 如果這個點被鬆弛過 N 次以上 代表存在負環
                    // 因為一個點最多跟 N-1 個點相連 最多更新 N-1 次
                    if(++cnt[e.v] >= N) return false;
                    
                    q.push(e.v);
                    inqueue[e.v] = true;
                }
            }
        }
    }
    return true;
}


int main(){
    int t;
    cin >> t;

    while(t--){
        cin >> N >> M;
        for(int i = 0; i <= N; ++i) G[i].clear();
        
        int u, v, w;
        for(int i = 0; i < M; ++i){
            cin >> u >> v >> w;
            // 有向圖
            G[u].push_back({v, w});
        }

        if(!SPFA(0)) cout << "possible" << endl;
        else cout << "not possible" << endl;
    }
}