首頁 Uva Problems

# 題目: UVa 11463 - Commandos

# 題目說明

有一群敢死隊，他們的目的是摧毀所有敵方建築
給一個無向圖，所有 edge 的 weight 皆為 1
求起點 s 經過最遠的點後到終點 d 的最短路徑

題目原意為需要經過所有的點，但是同時有複數個人從起點出發
所以可以改為從起點經過最遠的點最後到終點的問題

INPUT:
第一行輸入一個整數 T ，代表測資數
每筆測資先輸入兩個整數 N 與 R ，代表 N 個點中有 R 條線
接下來有 R 行，每行輸入兩個整數 u 、 v ，代表 u 連到 v (雙向)
最後有兩個整數 s 與 d ，代表起點與終點

OUTPUT:
輸出 起點 -> 最遠的點 -> 終點 的最短路徑

# 解題方法

先建圖

  1. 將所有點設為 101 (相當於此題的無限大)
  2. 將 G[u][v] 與 G[v][u] 設為 1 (一條連接 u 、 v 的路)
  3. 將 G[i][i] 設為 0 (自己走到自己)

接下來跑 Floyd-Warshall algorithm (佛洛依德演算法)
轉移方程為: G[i][j] = min(G[i][j], G[i][k] + G[k][j])

最後找出所有從起點 s 走到任意點 i ，再從任意點 i 走到終點 d 的 max

# 參考程式碼

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);
	int T, N, R, u, v;
	cin >> T;
	for (int cases = 1; cases <= T; ++cases)
	{
		cin >> N >> R;
		vector<vector<int>> G(N, vector<int>(N, 101));
		for (int i = 0; i < R; ++i)
		{
			cin >> u >> v;
			G[u][v] = 1;
			G[v][u] = 1;
		}
		for (int i = 0; i < N; ++i) G[i][i] = 0;
		// Floyd-Warshall algorithm
		for (int k = 0; k < N; ++k) for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j)
			G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
		int Max = 0, s, d;
		cin >> s >> d;
		for (int i = 0; i < N; ++i) Max = max(Max, G[s][i] + G[i][d]);
		cout << "Case " << cases << ": " << Max << "\n";
	}
	return 0;
}
# 參考資料
https://blog.csdn.net/mobius_strip/article/details/46605841