题目的大意是求所有点对之间最短路之和的平均值。要求所有点对之间的最短路（即全源最短路），并且数据范围很小。很容易想到使用 Floyd 算法。
Floyd 的实现（会用的可以跳过）
Floyd 本质上是一种动态规划。设 \(d_{i,j}\) 表示从 \(i\) 到 \(j\) 的最短路径的长度（注意题目输入为有向边，所以 \(d_{i,j}\) 与 \(d_{j,i}\) 的意义不一样），\(n\) 为最大点的编号。
初始时，若 \(i\) 到 \(j\) 之间存在有向边，那么 \(d_{i,j}=1\)（表示可以直接从 \(i\) 跳到 \(j\)），否则给 \(d_{i,j}\) 赋予一个大数即可（表示 \(i\)、\(j\) 之间没有直接连接，注意不要太大了，避免超出范围）。
考虑在求 \(i\) 到 \(j\) 的最短路时，枚举一个中转点 \(k\)，并且计算从 \(i\) 到 \(k\)，从 \(k\) 到 \(j\) 的最短路径之和，并用此更新 \(d_{i,j}\)，可以得到如下转移方程：
\[d_{i,j}=\min(d_{i,j},d_{i,k}+d_{k,j}) \]注意在实现 Floyd 时，应当先枚举 \(k\)（即中转点），再枚举 \(i\) 和 \(j\)（起点和终点），这样做可以保证 \(d_{i,k}\) 和 \(d_{k,j}\) 都被计算过，从而更新答案。
最后在统计时，只需求出所有点对之间的最短路之和，再除以计算过的点的次数之和，保留三位小数。
具体实现如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int d[101][101],n,ans,t,T;
int main()
{
while(true)
{
T++;
for(int i=1;i<=100;i++)
for(int j=1;j<=100;j++)
d[i][j]=0x3f3f3f3f;
int a,b;
n=0;
ans=0;
t=0;
while(true)
{
cin>>a>>b;
if(a==0&&b==0)
{
if(n==0) return 0;
else break;
}
d[a][b]=1;
n=max(n,max(a,b));
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j&&d[i][j]<0x3f3f3f3f)
{
t+=d[i][j];
ans++;
}
printf("Case %d: average length between pages = %.3f clicks\n",T,(t*1.0)/(ans*1.0));
}
return 0;
}