時間限制 2000 ms ・ 記憶體限制 256 MB
題目描述
把網頁視為有向圖節點，超連結由來源網頁指向目標網頁。一次點擊只能沿一條連結移動。 給定任意節點皆可到達其他任意節點的圖，求所有不同起點、終點的有序配對之最短路徑長度平均值。從自己到自己不列入平均。
輸入格式
每筆資料是一連串整數對 a b，代表 a 到 b 的連結，網頁編號為 1 至 100。每筆以 0 0 結束。最後再多一組 0 0，表示沒有任何連結的空資料並結束輸入。 不會有節點指向自己的直接連結，且每個節點保證能到達其他所有節點。
輸出格式
每筆一行，格式為 Case k: average length between pages = v clicks。k 從 1 起算，v 為平均最短路徑長度，固定小數點後三位。
題目來源：UVa 821 — Page Hopping。 原題：https://onlinejudge.org/external/8/821.pdf
範例測資
範例輸入 1
1 2 2 4 1 3 3 1 4 3 0 0 1 2 1 4 4 2 2 7 7 1 0 0 0 0
範例輸出 1
Case 1: average length between pages = 1.833 clicks Case 2: average length between pages = 1.750 clicks
請先登入後再提交程式碼
討論與題解
載入討論區…