題目: UVa - 821 - Page Hopping
題目說明
給一個有向圖,求所有可連通的任意兩點的最短路徑平均。
Input: 每組測資裡面有許多兩個數字的 pair,u
、v
,表示點 u
與點 v
連通,若皆為 0 表示該組測資結束,若測資的第一組 u
、v
皆為 0 表程式結束。
Output: 輸出所有可連通的任意兩點的最短路徑平均。
解題思路
All Pair Shortest Path 題,讀測資並做 Floyd-Warshall Algorithm 求解即可。需要注意的是點的編號並不是集中的,所以需要紀錄點的最大編號。
參考解法
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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66
| #include <bits/stdc++.h>
using namespace std;
static auto __ = [] { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0; }();
const int INF = (int)1e9;
int C; int dist[101][101]; int N; int u, v;
void init() { N = 1; for (int i = 1; i < 101; ++i) { for (int j = 1; j < 101; ++j) dist[i][j] = INF; dist[i][i] = 0; } }
void read() { do { dist[u][v] = 1; N = (max(max(u, v), N)); } while (cin >> u >> v && (u || v)); }
void FloydWarshall() { for (int k = 1; k <= N; ++k) { for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) dist[i][j] = min(dist[i][k] + dist[k][j], dist[i][j]); }
double sum = 0; int cnt = 0; for (int i = 1; i <= N; ++i) for (int j = 1; j <= N; ++j) if (dist[i][j] < INF && dist[i][j]) sum += dist[i][j], ++cnt;
cout << "Case " << ++C << ": average length between pages = "; cout << setprecision(3) << fixed << sum / cnt << " clicks\n"; }
int main() { while (cin >> u >> v && (u || v)) { init(); read(); FloydWarshall(); } }
|
參考資料
UVa 821 - Page Hopping_小白菜又菜-CSDN博客