# 題目: 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