UVa 821 - Page Hopping

題目：給你一個有向的地圖，求所有路徑（兩點間的最短路徑）的平均長度。

分析：圖論，最短路。利用floyd求解，然後將所有效的邊加和求平均值即可。

說明：距離700還有14題╮(╯▽╰)╭。

#include <cstring>
#include <cstdio>

int dist[101][101];
int oo = 100000001;

int main()
{
	int a, b, n, cases = 1;
	while (~scanf("%d%d",&a,&b) && a+b) {
		//initial
		for (int i = 0; i < 101; ++ i)
			for (int j = 0; j < 101; ++ j)
				dist[i][j] = oo;
		for (int i = 0; i < 101; ++ i)
			dist[i][i] = 0;
		//read data
		n = 0;
		do {
			dist[a][b] = 1;
			if (a > n) n = a;
			if (b > n) n = b;
		}while (~scanf("%d%d",&a,&b) && a+b);
		//floyd
		for (int k = 1; k <= n; ++ k)
			for (int i = 1; i <= n; ++ i)
				for (int j = 1; j <= n; ++ j)
					if (dist[i][j] > dist[i][k] + dist[k][j])
						dist[i][j] = dist[i][k] + dist[k][j];
		//output
		int count = 0, sum = 0;
		for (int i = 1; i <= n; ++ i)
			for (int j = 1; j <= n; ++ j)
				if (dist[i][j] < oo && dist[i][j]) {
					sum += dist[i][j];
					count ++;
				}
		
		printf("Case %d: ",cases ++);
		printf("average length between pages = %.3lf clicks\n",1.0*sum/count);
	}
    return 0;
}