UVa11463 - Commandos(Floyd)

題目大意

敢死隊們要去爆破敵隊的建築物，有 n 個建築物要爆破，從 A 到 B 建築物都需要花費時間，我們要將所有 n 個建築物都爆破完，敢死隊們會分工進行，可以分到 n 組，爆破時間不計入，我們會再 start 點出發、destination 點集合，想請問完成這個任務，最少要花多少時間

題目連結

重點觀念

• 演算法知識 - Floyd-Warshall algorithm (無權重、有權重向圖) by 大衛的筆記
• 因為可以分工進行，因此我們只要算從出發點到第 i 點 + 第 i 點到集合點距離最遠即可。，因為他們是最晚回來的一組

分析

• 做一次 floyd
• 對每一個點確認，輸出必須走最久的最短路徑

參考連結

UVa 11463 - Commandos by Ping

題目程式碼

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

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 120
#define int long long
#define INF 0x3f3f3f
using namespace std;
int t, n, r;
int u, v, c;
int start, destination, kase = 1;
int dist[MAXN][MAXN];

void floyd(){
    for(int k = 0; k < n; k++){
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }

}

void print(){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            printf("%10d ", dist[i][j]);
        }
        printf("\n");
    }
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> n >> r;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                dist[i][j] = INF;
            }
            dist[i][i] = 0;
        }
        for(int i = 0; i < r; i++){
            cin >> u >> v;
            dist[u][v] = 1;
            dist[v][u] = 1;
        }

        floyd();
        int ans = 0;
        cin >> start >> destination;
        for(int i = 0; i < n; i++){ //判斷從 start to i, i to destination 最久的距離是哪個，輸出他
            if(dist[start][i] + dist[i][destination] > ans){
                ans = dist[start][i] + dist[i][destination];
            }
        }
        //print();
        cout << "Case " << kase++ << ": " << ans << "\n";

    }
    return 0;
}