4619 . Diligent Mr. Tsai

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

Description

題目 PDF 檔在這裡

蔡哥非常邊緣，班上都沒有人揪他去看跨年煙火，所以他只好自己前往 101 看煙火。到了象山站後，場景只能說是 people mountain people sea。傻逼的他，完全找不到路。這時他突然想起自己化學老師的作業中寫過接近中心性的報告。

接近中心性 "--- 是指一個節點在網路中的緊密程度，可預期一個節點如果距離其他所有節點越近，它理當會處於較為中心的位置。計算方式非常簡單：該節點到其他所有節點的最短路徑長度取平均值。
因此，他決定利用這個概念來找到關鍵的地點，幫助自己順利看到煙火。

聰明的你，請幫助蔡哥寫一個程式計算吧。另外，因為蔡哥最近忘記除法運算怎麼做了。因此，你只需要輸出每個點到所有其他點的最短路徑長度總和即可。

Input Format

第一行有兩個正整數 $n,m$ ($1 \le n \le 3000$, $1 \le m \le 5000$) "--- 節點和邊的數量。

接下來有 $m$ 行，每行包含兩個整數 $u_i,v_i$ ($1\le u_i, v_i \le n$) "--- 有一條雙向邊連結 $u_i,v_i$ 兩點。

保證輸入的圖是一張沒有自環、重邊的簡單連通圖。

Output Format

輸出 $n$ 個數字，以空格隔開，分別為每個節點到其他所有節點的最短路徑長度和，數字之間以空格隔開。

Sample Input 1

5 8
3 4
1 2
4 5
2 3
3 5
1 3
1 5
2 4

Sample Output 1

5 5 4 5 5

Hints

Problem Source

TopCoder

AaW
學弟電爛我了

User's AC Ratio

100.0% (1/1)

Tags

小社賽 113 學年度

Problem Setter

Created by keaucucal

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 2
2 0~7 $1 \le n \le 50, \; m \le 100$ 18
3 0~16 $1 \le n \le 500, \; m \le 1000$ 30
4 0~24 無其他限制 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Memory Limit (RSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 262142 65536 1 2 3 4
1 1000 262144 262142 65536 2 3 4
2 1000 262144 262142 65536 2 3 4
3 1000 262144 262142 65536 2 3 4
4 1000 262144 262142 65536 2 3 4
5 1000 262144 262142 65536 2 3 4
6 1000 262144 262142 65536 2 3 4
7 1000 262144 262142 65536 2 3 4
8 1000 262144 262142 65536 3 4
9 1000 262144 262142 65536 3 4
10 1000 262144 262142 65536 3 4
11 1000 262144 262142 65536 3 4
12 1000 262144 262142 65536 3 4
13 1000 262144 262142 65536 3 4
14 1000 262144 262142 65536 3 4
15 1000 262144 262142 65536 3 4
16 1000 262144 262142 65536 3 4
17 1000 262144 262142 65536 4
18 1000 262144 262142 65536 4
19 1000 262144 262142 65536 4
20 1000 262144 262142 65536 4
21 1000 262144 262142 65536 4
22 1000 262144 262142 65536 4
23 1000 262144 262142 65536 4
24 1000 262144 262142 65536 4
Submit
Back to Top