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} < m i n (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

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (100%): 1.0s , <10M

提示：

標籤:

出處:

2019 NCTU PCCA Winter [管理者： emiliaistruelove@gmail.com

qqrainbow (愛蜜莉雅) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」