989 . 大型翻譯機
TopCoder
Tags
Description
經過多年的努力，偉大的多種族群島共和國（The Islands of Great Ethnic-diversity Republics, or Grand TIGER for short) 終於建國成功，人們朝世界和平又進了一步。
如同 TIGER 國的名稱所描述的，此國由 $N$ 個島嶼構成，其中有 $M$ 對島嶼之間以雙向連接的橋樑聯繫，第 $i$ 橋樑的長度為 $w_i$。 在這 $N$ 座島嶼之中有 $K$ 個住人的島嶼，每座住人的島嶼中都住著不同的種族，第 $i$ 座住人島嶼說著語言 $i$。雖然這個國家的和平的願景十分美好，但是因為這個國家的種族實在太多了，他們之間無法有效率的用各自的語言溝通。為了解決這個問題，TIGER 政府在其中一座無人島嶼（編號為 $1$ 的那座島）上，架設了一個巨型翻譯機器，從此之後群島中的人們可以透過以下方式互相溝通：
- 從第 $A$ 座住人島嶼將用語言 $A$ 寫成的信件送到島嶼 $1$ 上
- 島嶼 $1$ 將信件翻譯成語言 $B$。因為機器的限制，每一封信件只能在這裡從 $A$ 轉到 $B$，不能經過中間語言。
- 島嶼 $1$ 將翻譯的信件送到第 $B$ 座島嶼上
每用一次這種溝通方式，所付出的代價為 $dis(A,1) + dis(B,1) + v_{A,B}$ 其中 $dis(x,1)$ 為經過若干橋樑後由第 $x$ 座住人島嶼到島嶼 $1$ 的最小距離，而 $v_{A,B}$ 則為使用翻譯機將語言 $A$ 轉成語言 $B$ 的代價（注意這個 $v$ 可以是負的)。
若島 $A$ 想要跟島 $C$ 通訊，他們可以透過若干次的溝通達成，例如可以由島 $A$ 先將信寄給島 $B$，再由島 $B$ 轉寄給島 $C$，這樣的代價為每次溝通的代價之和，並定義最小通訊代價為所有溝通方式的最小代價總和。為了促進島嶼間的溝通，我們想要算出在這個溝通規則之下，全住人島嶼對之中最小通訊代價的最大值是多少。
Input Format
輸入第一行，此行輸入兩個整數 $N,M$ 表示有 $N$ 座島和 $M$ 個橋樑
接下來 $M$ 行，每一行有三個正整數 $a_i,b_i,w_i$ 表示第 $i$ 座橋樑是連接島嶼 $a_i$ 和 $b_i$，長度為 $w_i$
第 $M+2$ 行，此行輸入一個整數 $K$ 表示有 $K$ 個住人島嶼，也就是有 $K$ 個種族。
第 $M+3$ 行，此行輸入 $K$ 個相異整數，$k_i$ 表示第 $i$ 座住人島嶼的編號
接下來 $K$ 行，每一行有 $K$ 個整數，$v_{ij}$，表示翻譯機從第 $i$ 種語言轉到第 $j$ 種語言的代價是多少
- $ 1 \leq N \leq 10^ 6 $
- $ N-1 \leq M \leq \min(\frac{N(N-1)}{2},10^ 6)$
- $1 \leq a_i,b_i \leq N$
- $1 \leq w_i \leq 10^ 9$
- $2 \leq K \leq \min(N-1,500)$
- $2 \leq k_i \leq N$
- $-10^ 9 \leq v_{ij} \leq 10^ 9$
保證 TIGER 國中任意島嶼可以走到其他任意島嶼，且同一對島嶼之間不會有兩座橋
Output Format
輸出一個整數，表示在 $K$ 個島嶼之中寄信的最大代價是多少
但若最大成本不存在，輸出 -1
Sample Input 1
5 4 5 1 2 3 4 5 1 2 8 5 3 3 4 3 2 5 4 0 5 8 2 3 0 0 0 0 0 0 0 1 0 0 0
Sample Output 1
18
Sample Input 2
5 8 3 1 9 3 5 1 2 3 3 4 1 10 4 5 2 1 2 8 5 1 6 3 4 4 4 2 4 5 3 0 50 0 0 -45 0 0 0 0 0 0 0 0 0 0 0
Sample Output 2
-1
Hints
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資。 | 0 |
| 2 | 2~11 | $v_{ij}=0$ | 20 |
| 3 | 0~31 | 無特別限制。 | 80 |