e297: PD. Demand(居民的請求)
Tags :
Accepted rate : 8人/9人 ( 89% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-07-04 18:49

Content

有$A$、$B$ 兩個國家,裡⾯分別有$n_1$、$n_2$ 個城市。同個國家的城市之間必有雙向的路(分別有$m_1$、$m_2$條)可以⾛到,但是有不同的⾞費。因為$A$跟$B$是很友好的國家,居⺠們想要各⾃建⼀個港⼝互通,且已知不管建在哪裡船費都是1000。現在$A$、$B$國家分別有$t_1$個跟$t_2$個預計要建成港⼝的濱海城市。請幫他們各⾃從中選⼀個,讓居⺠們從$A$國任⼀城市到$B$國任⼀城市可能的最⼤花費最⼩,並輸出此花費。

Input

第⼀⾏有三個數字,分別是$n_1$、$t_1$、$m_1$。下⼀⾏有$t_1$個數字,代表$A$國可能建成港⼝的城市。再接下來$m_1$⾏,每⾏有$u$、$v$、$c$ 三個數字,代表$A$國城市$u$和城市$v$之間有⼀條雙向的道路,⾞費為$c$。再下⼀⾏為$n_2$、$t_2$、$m_2$。接著是$t_2$個數字,代表$B$國可能建成港⼝的城市。最後$m_2$ ⾏,每⾏有$u$、$v$、$c$ 三個數字,代表$B$國城市$u$和城市$v$之間有⼀條雙向的道路,⾞費為$c$。

$2 < n_1, n_2 < 10000$
$1 \leq t_i < min(n_i, 30), i = 1, 2$
$n_i \leq  m_i < n_i^2, i = 1, 2$
$1 \leq c \leq 1000$

Output

請輸出選擇最適當的港⼝後,居⺠們從$A$國任⼀城市到$B$國任⼀城市可能的最⼤花費的最⼩值。

Sample Input
4 2 5
3 4
1 2 20
3 1 10
3 2 10
2 4 20
3 4 15
3 3 2
1 2 3
1 2 15
3 2 20
Sample Output
1035
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <10M
Hint :
Tags:
出處:
2019 NCTU PCCA Winter [管理者:
qqrainbow (愛蜜莉雅)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」