Problem Solving►UVa

Uva 821 - Page Hopping

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

Solution

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

Code

UVa 821
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#include<algorithm>
#define N 101
using namespace std;

int main()
{
    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);

        //Floyd-Warshall
        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 clicks\n", Case++, (float)sum / count);
    }

    return 0;
}