UVa318 - Domino Effect(Dijkstra)

題目大意：

Domino Effect 指一件事的發生會產生一連串的連鎖反應，但這不是我們的重點XD。

我們的重點就如題目，給你一張骨牌的圖，並告訴你關鍵點以及從此關鍵點到下一個關鍵點的秒數。然後我們想要推動其中一個關鍵點，來讓圖上所有的骨牌倒塌，想請問是在第幾秒的時候全部倒塌，在那一個關鍵點開始倒榻。

關鍵點: 可以影響到兩個骨牌以上的骨牌。
秒數的一個小提示，假如最後倒塌是從兩個關鍵點一起倒榻時則計算秒數方式如下 \(0.5(起點到關鍵點一 + 起點到關鍵點二 + 關鍵點一至關鍵點二)\)

這題的測試資料有個問題，最後一筆是只有一個 0，因此在判斷時，只要判斷 N 是否為 0 即可，如果全部都判斷反而會有錯誤(cin 的情況，因為我是用 cin )。

分析：

這題有點小難，一開始的時候我不太懂這題需要使用到 Dijkstra，我想說應該是用洪水法去解出，但後來發現洪水法的話雖然一樣可以得出單緣最短路徑，但並不好寫，至少需要開兩張一樣大的圖，查網路上後知道這題用 Dijkstra 更好，要是沒有查的話可能會浪費時間寫，還要再重改八QQ。

用 adjecency matrix 會更好寫，如果用 Piority 來寫的話會發現其實沒有那麼好寫，思考邏輯會比較混亂，於是 Dijkstra 就用 adjecency matrix 寫。

我們先算出最長的最短路徑(找出最後一個骨牌落下的時間，並定義 max_path )，同時並記錄每一個關鍵點的最短路徑(跌落秒數)，再來我們透過 burte force 的方式將每一個連接邊去揣測，如果可以揣測出比 max_path 更大的跌落秒數就表示此骨牌應該是兩個關鍵點同時跌落而不是當最後一個點跌落結束全部都結束。

參考來源

UVa 318 - Domino Effect（zoj 1298
【UVa】318-Domino effect (Dijkstra, Single source shortest path)

題目程式碼

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 520
#define oo 1e20
using namespace std;
int kase=0 , N , M ;
int a , b , v , x , st , ed , flag , now   ;
double graph[MAXN][MAXN] ;
int used[MAXN] ;
double max_path , speed[MAXN] ; //speed = start to each node shortest path 

void dijkstra(){
    speed[1] = 0 ;
    used[1] = 1;
    now = 1 ;
    for(int i = 1 ; i <= N ; i++){
        for(int j = 1 ; j <= N ; j++){
            if(graph[now][j] && speed[j] > graph[now][j] + speed[now] ){
                speed[j] = graph[now][j] + speed[now];
                //cout << speed[j] << '\n' ;
            }
        }
        max_path = oo ;
        for(int j = 1 ; j <= N ; j++){
            if( !used[j] && max_path > speed[j]){
                max_path = speed[j] ;
                now = j;
            }
        }
        //cout << "i is " << i << ' ' << now << ' ' << max_path << '\n' ;
        used[now] = 1 ;
    }

}

int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
    freopen("out.txt" , "w" , stdout );
#endif // LOCAL
    while(cin >> N >> M && N ){
        for(int i = 1 ; i <= N ; i++){
            for(int j = 1 ; j <= N ; j++) graph[i][j] = 0 ;
            speed[i] = oo ;
            used[i] = 0 ;
        }

        for(int i = 1 ; i <= M ; i++){
            cin >> a >> b >> v ;
            graph[a][b] = v ;
            graph[b][a] = v ;
        }

        flag = 0 ;
        dijkstra() ;
        max_path = speed[now];

        for(int i = 1 ; i <= N ; i++){
            for(int j = i+1 ; j <= N ; j++){
                if(graph[i][j]  &&max_path < 0.5 * (speed[i] + speed[j] + graph[i][j])){
                    max_path = 0.5 * (speed[i] + speed[j] + graph[i][j]) ;
                    st = i ;
                    ed = j ;
                    flag = 1 ;
                    break;
                }
            }
        }

        cout << "System #" << ++kase << '\n' ;
        if(flag == 1 ){
            cout << "The last domino falls after " << fixed << setprecision(1) << max_path
             << " seconds, between key dominoes " << st <<" and " << ed << ".";
        }
        else
            cout << "The last domino falls after " << fixed << setprecision(1) << max_path << " seconds, at key domino " << now << "." ;
        cout << "\n\n" ;

     }
    return 0;
}