Problem : 83 - FOMI洗腦計畫

Problem Statistics

Solved Member: 22　　Submission: 56　　User Tried: 22

Statement:

FOMI要來對JOI國洗腦了！！

JOI國是由N個城市所組成的，並且由M條互不相交的雙向道路連結城市與城市之間。N個城市當中，有K個城市已經被FOMI佔領了。國家的人民們會到附近有FOMI的城市來購物。

由於每個人家旁邊不一定都有一家FOMI，要大遙遠來到附近FOMI可不是一件容易的事情！因為有些客人可能因為路途太遙遠而不小心迷路到旁邊的11-7去。FOMI的經理對於如何壟斷這個國家的市場非常感興趣，他決定蓋新的分店。在這之前，他必須先考慮究竟哪一戶人家是離最近的FOMI是最遠的。由於每戶人家除了蓋在城市以外，也有可能在道路的中間，這可是一項艱鉅的任務，所以FOMI的經理毫不猶豫的聘請整個鎮上最優秀的程式設計師，你來幫他的忙。

Task:

給你城市，道路間的關係，以及FOMI的分店位置。請你回答出距離最近FOMI最遠的那戶人家的距離。

Input:Output:

第1行有N, M, K 3個整數，由空白分隔開來。分別代表城市數量，道路數量，以及FOMI的分店數量。

接下來M行每行有3個整數，Ai, Bi, Ci(1 ≤ Ai, Bi ≤ N; 1 ≤ Ci ≤ 1000)，以空白分隔開來，代表Ai都市以及Bi都市之間有一條長度為Ci的道路所連接，並且你可以假設相同的兩都市之間只會有一條道路相連。

接下來的K行每行有1個正整數Si(1 ≤ Si ≤ N)，代表FOMI在Si的地方有一家分店。

輸出一行整數，代表距離FOMI最遠那戶人家走去FOMI所需的距離，如果是小數，請四捨五入之後輸出。

Sample Input:Sample Output:

SAMPLE A:
3 3 1
1 2 1
2 3 1
3 1 1
1

SAMPLE B:
4 5 2
1 2 4
1 3 1
2 3 2
2 4 2
3 4 1
2
4

SAMPLE A:
2

SAMPLE B:
3

HINT:

2 ≤ N ≤ 3000，其中N代表JOI國當中城市的數量
1 ≤ M ≤ 100000 = 10^5，代表JOI國當中道路的數量
1 ≤ K ≤ N，K代表FOMI的分店數量
1 ≤ Ci ≤ 1000，Ci代表第i條道路的長度

40%測資滿足： K = 1

對於SAMPLE A:每條道路長度皆為1，且FOMI只有在城市1才有分店。
離FOMI最遠的地方在第2個城市以及第3個城市的中間，距離為1.5，因此四捨五入之後輸出2。

SAMPLE A的圖。

Source:

JOI 2010/2011 本選

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	2500ms	65536kb
0-2	2500ms	65536kb
1-1	2500ms	65536kb	10
1-2	2500ms	65536kb
1-3	2500ms	65536kb
2-1	2500ms	65536kb	10
2-2	2500ms	65536kb
3-1	2500ms	65536kb	10
3-2	2500ms	65536kb
4-1	2500ms	65536kb	10
4-2	2500ms	65536kb
5-1	2500ms	65536kb	10
5-2	2500ms	65536kb
5-3	2500ms	65536kb
6-1	2500ms	65536kb	10
6-2	2500ms	65536kb
6-3	2500ms	65536kb
7-1	2500ms	65536kb	10
7-2	2500ms	65536kb
8-1	2500ms	65536kb	10
8-2	2500ms	65536kb
9-1	2500ms	65536kb	10
9-2	2500ms	65536kb
9-3	2500ms	65536kb
10-1	2500ms	65536kb	10
10-2	2500ms	65536kb
10-3	2500ms	65536kb