TopCoder

asuka
酸欠少女

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

62.5% (10/16)

Tags

Description

現在有一張 N 個點 M 條邊的無向圖,代表有 N 個城市(編號 1N),由 M 條道路連接。
每條道路都有各自的長度,兩個城市 st 的距離為從 st 要經過的所有道路長度總和。
注意有可能不存在任何道路可以從某個城市 s 出發抵達另個城市 t

現在請你輸出從每座城市出發,在行駛距離不超過 K 的前提下,能到達哪些城市?

Input Format

第一行包含三個整數 N, M, K 以空白隔開,代表有 N 座城市,有 M 條道路
第二行至第 M+1 行,每行有三個數字 a, b, c 以空白隔開,代表城市 a 和城市 b 之間有一條長度為 c 的雙向道路。

  • 3N500
  • 1MN(N1)2
  • 1K109
  • 1a,bNab
  • 1c104
  • 所有 (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

Subtasks

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