TopCoder

asuka

酸欠少女

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

62.5% (10/16)

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

Sample Output 1

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

Hints

Problem Source

No.	Testdata Range	Constraints	Score
1	0	範例測資	0
2	0~15	無額外限制	100

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (VSS, KiB)	Output Limit (KiB)	Subtasks
0	1000	524288	65536	1 2
1	1000	524288	65536	2
2	1000	524288	65536	2
3	1000	524288	65536	2
4	1000	524288	65536	2
5	1000	524288	65536	2
6	1000	524288	65536	2
7	1000	524288	65536	2
8	1000	524288	65536	2
9	1000	524288	65536	2
10	1000	524288	65536	2
11	1000	524288	65536	2
12	1000	524288	65536	2
13	1000	524288	65536	2
14	1000	524288	65536	2
15	1000	524288	65536	2

778 . 全點對最短路