UVa10354 - Avoiding Your Boss(Floyd)

題目大意

你是一個悠閒但優秀的程式設計師，有一天，你裝病請假，但你想出門到超市買東西，你要避免遇到老闆，老闆會從老闆家會走路徑到辦公室，其中老闆一定會走最短路徑，那你的任務則是避開老闆走的最短路徑中所有節點，再讓你自己走最短路徑抵達超市。

請輸出自己走最短路徑抵達超市的成本，不行請輸出 “MISSION IMPOSSIBLE.”

題目連結

重點觀念

• 演算法知識 - Floyd-Warshall algorithm (無權重、有權重向圖) by 大衛的筆記
• 如果從老闆家到辦公室，可能有複數的最短路徑，那都要避開

分析

• 首先寫一個 floyd 找出老闆的所有最短路徑
• 確認每一個點老闆會不會經過，經過就紀錄，定義 ban[i]
  • 判斷每一個點是不是最短路徑 dist1[BH][i] + dist1[i][OF] == dist1[BH][OF]
  • 如果成立，那就是老闆會經過的點
• 再做一個 floyd，但是避免 ban[i]
• 之後直接輸出答案

參考連結

Avoiding Your Boss by 台長

心得

以前都沒有想過 floyd 可以做到這些操作，現在學到了。好開心

希望我可以多應用一些演算法在日常生活上，才不會白費自己學到。

題目程式碼

有一些程式碼註解在 演算法知識 - Floyd-Warshall algorithm (無權重、有權重向圖) by 大衛的筆記 請供參考。

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 120
#define INF 0x3f3f3f
using namespace std;
int P, R, BH, OF, YH, M;
int u, v, c;
int dist1[MAXN][MAXN], dist2[MAXN][MAXN]; //dist1 老闆家到辦公室、dist2 自己家到超市
int ban[MAXN]; //老闆可能會經過的節點


void floyd(){
    for(int k = 1; k <= P; k++){
        for(int i = 1; i <= P; i++){
            for(int j = 1; j <= P; j++){
                if(dist1[i][k] + dist1[k][j] < dist1[i][j])
                    dist1[i][j] = dist1[i][k] + dist1[k][j];
            }
        }
    }

}

void floyd2(){
    for(int k = 1; k <= P; k++){
        if(ban[k]) continue; //老闆可能會經過的節點，要避開
        for(int i = 1; i <= P; i++){
            if(ban[k]) continue;
            for(int j = 1; j <= P; j++){
                if(ban[k]) continue;
                if(dist2[i][k] + dist2[k][j] < dist2[i][j])
                    dist2[i][j] = dist2[i][k] + dist2[k][j];
            }
        }
    }

}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    while(cin >> P >> R >> BH >> OF >> YH >> M){
        for(int i = 1; i <= P; i++){
            for(int j = 1; j <= P; j++){
                dist1[i][j] = INF;
                dist2[i][j] = INF;
            }
            dist1[i][i] = 0;
            dist2[i][i] = 0;
            ban[i] = 0;
        }

        for(int i = 0; i < R; i++){
            cin >> u >> v >> c;
            dist1[u][v] = c;
            dist1[v][u] = c;

            dist2[u][v] = c;
            dist2[v][u] = c;
        }

        floyd(); //老闆家到辦公室
        for(int i = 1; i <= P; i++){ 
            //如果從老闆家 到 i 點在到辦公室跟最短距離相同，那就是老闆會經過的節點
            if(dist1[BH][i] + dist1[i][OF] == dist1[BH][OF])
                ban[i] = 1;
        }

        floyd2(); //自己家到超市
        //如果 dist2 無法抵達或超市、自己家老闆都會通過，那就沒辦法
        if(dist2[BH][OF] == INF || ban[YH] || ban[M]) cout << "MISSION IMPOSSIBLE.\n";
        else cout << dist2[YH][M] << "\n"; //輸出答案

    }

    return 0;
}