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