778 . 全點對最短路
TopCoder
Tags
Description
現在有一張 $N$ 個點 $M$ 條邊的無向圖，代表有 $N$ 個城市（編號 $1$ 到 $N$），由 $M$ 條道路連接。
每條道路都有各自的長度，兩個城市 $s$ 和 $t$ 的距離為從 $s$ 到 $t$ 要經過的所有道路長度總和。
注意有可能不存在任何道路可以從某個城市 $s$ 出發抵達另個城市 $t$。
現在請你輸出從每座城市出發，在行駛距離不超過 $K$ 的前提下，能到達哪些城市？
Input Format
第一行包含三個整數 $N$, $M$, $K$ 以空白隔開，代表有 $N$ 座城市，有 $M$ 條道路
第二行至第 $M+1$ 行，每行有三個數字 $a$, $b$, $c$ 以空白隔開，代表城市 $a$ 和城市 $b$ 之間有一條長度為 $c$ 的雙向道路。
- $3 \le N \le 500$
- $1 \le M \le \frac{N(N-1)}{2}$
- $1 \le K \le 10^ 9$
- $1 \le a,b \le N$ 且 $a \neq b$
- $1 \le c \le 10^ 4$
- 所有 $(a, b)$ 的無序對（順序不重要，$(a, b)$ 和 $(b, a)$ 視為相同）不重覆。
Output Format
輸出 $N$ 行。
第 $i$ 行輸出從編號為 $i$ 的城市出發，在行駛距離不超過 $K$ 的前提下，能到達的城市編號。
城市編號請由小到大輸出並以空白隔開。
Sample Input 1
5 6 3
1 5 3
1 3 3
1 4 1
2 3 1
2 4 1
4 5 3
1 5 3
1 3 3
1 4 1
2 3 1
2 4 1
4 5 3
Sample Output 1
1 2 3 4 5
1 2 3 4
1 2 3 4
1 2 3 4 5
1 4 5
1 2 3 4
1 2 3 4
1 2 3 4 5
1 4 5
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~15 | 無額外限制 | 100 |