e297.
PD. Demand(居民的請求)
內容
有$A$、$B$ 兩個國家，裡⾯分別有$n_1$、$n_2$ 個城市。同個國家的城市之間必有雙向的路（分別有$m_1$、$m_2$條）可以⾛到，但是有不同的⾞費。因為$A$跟$B$是很友好的國家，居⺠們想要各⾃建⼀個港⼝互通，且已知不管建在哪裡船費都是1000。現在$A$、$B$國家分別有$t_1$個跟$t_2$個預計要建成港⼝的濱海城市。請幫他們各⾃從中選⼀個，讓居⺠們從$A$國任⼀城市到$B$國任⼀城市可能的最⼤花費最⼩，並輸出此花費。
輸入說明
第⼀⾏有三個數字，分別是$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$
輸出說明
請輸出選擇最適當的港⼝後，居⺠們從$A$國任⼀城市到$B$國任⼀城市可能的最⼤花費的最⼩值。
範例輸入
#1
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
範例輸出
#1
1035
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (100%): 1.0s , <10M
公開 測資點#0 (100%): 1.0s , <10M
提示 ：
標籤:
出處:
2019 NCTU PCCA Winter
[管理者：
qqrainbow
(愛蜜莉雅)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||