778 . 全點對最短路

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

asuka
酸欠少女

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

62.5% (10/16)

Tags

apcsc apcsc-graph

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≤N≤500
  • 1≤M≤N(N−1)2
  • 1≤K≤109
  • 1≤a,b≤N 且 a≠b
  • 1≤c≤104
  • 所有 (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
Submit
Back to Top