# 題目: UVa 821 - Page Hopping

# 題目說明

求u與v最短路徑的加總，再除以u與v的組合數
(u與v屬於G中任意兩點)

---

INPUT:
每次輸入兩個整數u與v，代表u連到v，直到u與v為0
若u與v的第一次輸入皆為0，結束程式

---

OUTPUT:
輸出u與v最短路徑的加總，再除以u與v的組合數

# 解題方法

定義一個vector<vector<int>> G，G[i][j]代表從i到j的最短路徑
先將G中所有元素設為101，相當於無限大 (題目限制範圍為1 ~ 100)
將G[u][v]設為1，代表weight

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

最後將u與v最短路徑加總
並算出u與v的組合數 = 不重複元素的size * (不重複元素的size - 1)
相除後即可輸出

# 參考程式碼

#include <iostream>
#include <vector>
#include <unordered_set>
#include <iomanip>
#include <climits>

using namespace std;

int main()
{
	// fast io
	ios::sync_with_stdio(false);
	cout.tie(nullptr);
	cin.tie(nullptr);

	int u, v, cases = 0;
	vector<vector<int>> G(101);
	unordered_set<int> S;

	while (cin >> u >> v, u && v)
	{
		// init
		for (int i = 0; i < G.size(); ++i) G[i].assign(101, 101);
		S.clear();
		double ans = 0;
		int Max = 0;

		do
		{
			G[u][v] = 1;
			Max = max(Max, max(u, v));
			S.emplace(u);
			S.emplace(v);

		} while (cin >> u >> v, u && v);

		// Floyd-Warshall algorithm
		for (int k = 1; k <= Max; ++k) for (int i = 1; i <= Max; ++i) for (int j = 1; j <= Max; ++j)
			G[i][j] = min(G[i][j], G[i][k] + G[k][j]);

		int Size = S.size() * (S.size() - 1);
		for (auto i = S.begin(); i != S.end(); ++i) for (auto j = S.begin(); j != S.end(); ++j)
			if (*i != *j) ans += G[*i][*j];

		cout << "Case " << ++cases << ": average length between pages = " << setprecision(3) << fixed << ans / Size << " clicks\n";
	}

	return 0;
}

# 參考資料

https://www.pinghenotes.com/UVa-12319-Edgetown-s-Traffic-Jams/