POJ3259——SPFA的DFS優化判斷負環

題目描述：

耳機樓裡有很多教室，這些教室由雙向走廊連接配接。另外，還存在一些單向的秘密通道，通過它們可以回到過去。現在有 N (1 ≤ N ≤ 500) 個教室，編号 1..N, M (1 ≤ M ≤ 2500) 條走廊，和 W (1 ≤ W≤ 200) 條秘密通道。

DY在養貓之餘，還是一個時間旅行愛好者。她希望從一間教室出發，經過一些走廊和秘密通道，回到她出發之前的某個時間。

共有F (1 ≤ F ≤ 5) 組資料。對每組資料，判斷DY是否有回到過去的可能性。不存在耗時超過10,000秒的走廊，且不存在能帶DY回到10,000秒之前的秘密通道。

Input

首先是一個整數F，表示接下來會有F組資料。

每組資料第1行：分别是三個空格隔開的整數：N，M和W

第2行到M+1行：三個空格分開的數字（S，E，T）描述雙向走廊：從S到E需要耗費T秒。兩個教室可能由一個以上的路徑來連接配接。

第M +2到M+ W+1行：三個空格分開的數字（S，E，T）描述秘密通道：從S到E可以使時間倒流T秒。

OutputF行，每行對應一組資料。 每組資料輸出單獨的一行，” YES”表示能滿足要求，”NO”表示不能滿足要求。Sample Input

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8      

Sample Output

NO
YES      

代碼：

//
//  main.cpp
//  POJ3259
//
//  Created by jinyu on 2018/7/13.
//  Copyright © 2018年 jinyu. All rights reserved.
//

#include <iostream>
#include <queue>


using namespace std;


const int INF = 0x3f3f3f3f;
int visited[500+2];
int arc[500+2][500+2];
int dist[500+2];
int b[500+2][500+2];
int flag = 0;
int N;


void SPFAdfs(int start){
    if(flag) return;
    visited[start] = 1;
    for(int i = 1;i<=b[start][0];i++){
        if(dist[b[start][i]] > dist[start] + arc[start][b[start][i]]){
            dist[b[start][i]] = dist[start] + arc[start][b[start][i]];
            if(visited[b[start][i]]){
                flag = 1;
            }
            else{
                SPFAdfs(b[start][i]);
            }
        }
    }
    visited[start] = 0;
}

int main(){
    int F;
    cin>>F;
    while(F--){
        int M,W;
        cin>>N>>M>>W;
        for(int i = 1;i<=N;i++){
            dist[i] = INF;
            visited[i] = 0;
            b[i][0] = 0;
            for(int j = 1;j<=N;j++){
                if(i==j)
                    arc[i][j] = 0;
                else
                    arc[i][j] = INF;
            }
        }
        int mm = M;
        while(mm--){
            int S,E,T;
            cin>>S>>E>>T;
            if(T<arc[S][E]){
                arc[S][E] = T;
                arc[E][S] = T;
                b[S][0]++;
                b[E][0]++;
                b[S][b[S][0]] = E;
                b[E][b[E][0]] = S;
                
            }
        }
        int ww = W;
        while(ww--){
            int S,E,T;
            cin>>S>>E>>T;
            arc[S][E] = -T;
            b[S][0]++;
            b[S][b[S][0]] = E;
        }
        
        
        dist[1] = 0;
        SPFAdfs(1);

        if(flag)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
        flag = 0;
    }
    return 0;
}
           

題目本身不難，主要是SPFA的dfs優化來判斷負環。但是有很多細節：

1. 第一次打時數組初始化敲錯，也沒有注意到題目中的點下标是從1開始的。

2.習慣性采用鄰接矩陣去做，但其實會TLE，應該采用鄰接表（這裡我隻是簡單加了數組b來存儲鄰接資訊）。

3.測試資料貌似都是連通圖，如果是非連通的似乎應該對每個點SPFA。

4.memset的問題。