uva 821 - Page Hopping

 1 /*
 2  Problem link
 3  Type: Graph
 4  Algorithm:
 5      Use floyd to find all pair shortest path, sum them up, divide to the number of pair
 6      I use the map to mark for the vertex in the input.
 7  */
 8  #include <iostream>
 9  #include <cstdio>
10  #include <cstring>
11  #include <cmath>
12  #include <cstdlib>
13  #include <map>
14  using namespace std;
15  
16  const int maxn = 110;
17  const int oo = 2000000;
18  
19  double solve();
20  
21  int a[maxn][maxn];
22  int n;
23  map<int, int> list;
24  
25  int main()
26  {
27      pair<map<int,int>::iterator, bool> checkpair;
28      int u, v, test = 0;
29      while (true)
30      {
31          for (int i=0; i<maxn; i++)
32              for (int j=0; j<maxn; j++) a[i][j] = oo;
33          cin >> u >> v;
34          list.clear();
35          if (u==0 && v==0) break;
36          test++;
37          n = 0;
38          while (true)
39          {
40              checkpair = list.insert(pair<int,int>(u,n+1));
41              if (checkpair.second) n++;
42              u = checkpair.first->second;
43              checkpair = list.insert(pair<int,int>(v,n+1));
44              if (checkpair.second) n++;
45              v = checkpair.first->second;
46              a[u][v] = 1;
47              cin >> u >> v;
48              if (u==0 && v==0) break;
49          }
50          for (int i=1; i<=n; i++) a[i][i] = 0;
51  
52          printf("Case %d: average length between pages = %.3lf clicks\n",test,solve());
53      }
54      return 0;
55  }
56  
57  double solve() {
58      int sum = 0;
59      for (int k=1; k<=n; k++)
60          for (int i=1; i<=n; i++)
61              for (int j=1; j<=n; j++)
62                  if (a[i][j]>a[i][k]+a[k][j]) a[i][j] = a[i][k]+a[k][j];
63      for (int i=1; i<=n; i++)
64          for (int j=1; j<=n; j++) sum += a[i][j];
65      return(sum*1.0/(n*(n-1)));
66  }