首页 > itarticle > uva 821 – page hopping

uva 821 – page hopping

admin 11月 12, 2020 0

Contents

Problem

題目網址
 中文網址

Solution

先將每個點 map 到對應的 idx ，方便待會處理。
做 Floyd-warshall 後，將每個點到點之間的最短路徑相加，再除以路徑數即可。(注意不包含自己到自己)

Code


#include<algorithm>
#define N 101
using namespace std;

int ()
{
    int map[N], d[N][N], u, v, Case = 1;

    while (scanf("%d%d", &u, &v) && u&&v)
    {
        int i, j, k, idx = 0;
        for (i = 0; i < N; i++)
            fill(d[i], d[i] + N, 1e9);
        fill(map, map + N, 0);

        do
        {
            if (!map[u])
                map[u] = ++idx;
            if (!map[v])
                map[v] = ++idx;

            d[map[u]][map[v]] = 1;
        } while (scanf("%d%d", &u, &v) && u&&v);

        
        for (k = 0; k <= idx; k++)
            for (i = 0; i <= idx; i++)
                for (j = 0; j <= idx; j++)
                    if (i != j&&d[i][k] + d[k][j] < d[i][j])
                        d[i][j] = d[i][k] + d[k][j];

        int sum = 0, count = 0;
        for (i = 0; i <= idx; i++)
            for (j = 0; j <= idx; j++)
                if (d[i][j] < 1e9)
                {
                    sum += d[i][j];
                    count++;
                }

        printf("Case %d: average length between pages = %.3f clicksn", Case++, (float)sum / count);
    }

    return 0;
}