120 . 高速公路維修站

Submit
Status
Ranklist
Back to Problems List

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

22.2% (4/18)

Tags

2021 高階競技程式設計 - Contest #6

Description

你是高速公路行控中心的工作人員，
這個高速公路由 $N$ 個休息站與 $M$ 條道路組成，
每條道路連接兩個休息站，
且兩個休息站可以互相經由此道路連通。
為了維持交通順暢，
你希望計算每個休息站到最近的維修站有多遠，
你可以寫一個程式幫助計算嗎？

Input Format

第一行有三個整數 $N,M,F$，分別代表高速公路休息站、道路、維修站的數量。
接下來 $M$ 行，每行有三個整數 $u,v,w$，分別代表道路兩端點以及道路長度。
接下來一行有 $F$ 個整數，代表有維修站的休息站編號。

  • $1\leq N\leq10^5$
  • $1\leq M\leq2\times10^5$
  • $1\leq F,u,v\leq N$
  • $u\neq v$
  • $1\leq w\leq 10^9$
  • 有維修站的休息站編號不會重複

Output Format

輸出 $N$ 個數字，第 $i$ 個數字代表 $i$ 號休息站最近的維修站多遠，若沒辦法到任何維修站則輸出 $-1$。

Sample Input 1

10 13 2
2 8 8
1 4 4
4 3 4
3 7 7
6 1 15
7 1 2
4 5 8
8 7 9
7 5 3
10 1 12
5 10 13
4 9 4
3 6 10
9 2

Sample Output 1

8 0 8 4 12 18 10 8 0 20

Sample Input 2

15 14 4
11 1 17
8 9 14
3 7 28
3 10 10
2 13 24
9 11 17
3 12 25
11 2 29
11 14 7
11 3 18
7 5 16
11 5 7
6 4 21
7 11 7
1 2 11 14

Sample Output 2

0 0 18 -1 7 -1 7 31 17 28 0 43 24 0 -1

Hints

Problem Source

Subtasks

No. Testdata Range Score
1 0~32 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1
5 1000 65536 65536 1
6 1000 65536 65536 1
7 1000 65536 65536 1
8 1000 65536 65536 1
9 1000 65536 65536 1
10 1000 65536 65536 1
11 1000 65536 65536 1
12 1000 65536 65536 1
13 1000 65536 65536 1
14 1000 65536 65536 1
15 1000 65536 65536 1
16 1000 65536 65536 1
17 1000 65536 65536 1
18 1000 65536 65536 1
19 1000 65536 65536 1
20 1000 65536 65536 1
21 1000 65536 65536 1
22 1000 65536 65536 1
23 1000 65536 65536 1
24 1000 65536 65536 1
25 1000 65536 65536 1
26 1000 65536 65536 1
27 1000 65536 65536 1
28 1000 65536 65536 1
29 1000 65536 65536 1
30 1000 65536 65536 1
31 1000 65536 65536 1
32 1000 65536 65536 1
Submit
Status
Ranklist
Back to Top