250 . 產品配送問題
TopCoder
Tags
Description
IOICamp 聯邦由兩大國家組成：A 國以及 B 國。A 國中有 $N$ 個城市，而 B 國中有 $M$ 個城市，其中 A 國的城市（簡稱 A 城市）由 $1$ 到 $N$ 編號，而 B 國的城市（簡稱 B 城市）由 $N + 1$ 到 $N + M$ 編號。
每個城市都有一個工廠，A 城市的工廠可以生產 A 產品，B 城市的工廠可以生產 B 產品。當然，讓一個工廠開始運作不是一件容易的事，所以必須要花 $f_i$ 元才可以讓第 $i$ 個城市的工廠開始運作，一但一個工廠開始運作，它便可以生產無限量的產品。
這些城市們由 $K$ 個道路相連接，而產品可以藉由這些道路從一個城市運輸到另一個城市。不過，由於 B 國的工廠不能生產 A 產品，想當然爾，B 國之間的道路（連接兩個 B 城市）並不能運輸 A 產品。同樣的，A 國之間的道路也不能運輸 B 產品。此外，這些產品也不能「跨國轉運」，也就是不能將 B 產品從 B 城市傳到 A 城市，再「轉運」回另一個 B 城市，同樣的也不能有 A $\to$ B $\to$ A 這樣的運輸。
每條道路一開始都是封閉的，要第 $i$ 個道路開始運輸產品必須花上 $c_i$ 元。由於 A 產品以及 B 產品都是生活必需品，因此你希望花最少的錢，使得每個城市都能擁有 A 產品以及 B 產品。
Input Format
輸入第一行有三個整數 $N, M, K$ ，代表 A 城市的數量、 B 城市的數量以及道路的數量。
接著一行有 $N$ 個正整數，代表在 A 城市中設置工廠所需的花費。
接著一行有 $M$ 個正整數，代表在 B 城市中設置工廠所需的花費。
接著 $K$ 行，第 $i$ 行有三個正整數 $u_i, v_i, c_i$ ，代表一條連接 $u_i$ 以及 $v_i$ 的道路，且需要花費 $c_i$ 來使它運作。
- $1 \leq N, M \leq 100$
- $0 \leq K \leq \frac{(N + M) \times (N + M - 1)}{2}$
- $1 \leq u_i, v_i \leq N + M$
- $1 \leq f_i, c_i \leq 10000$
- 保證沒有重邊以及自環
Output Format
輸出一個整數，代表最少花費。若不可能達成，則輸出 -1。
Sample Input 1
7 1 1 7
3 10 7 4
2 8 9
4 2 10
5 1 4
2 3 4
7 6 8
4 1 3
6 5 4
6 4 10
3 1 7
4 8 10
3 8 5
3 7 2
5 3 3
7 2 6
4 5 2
8 1 6
6 3 2
Sample Output 1
Sample Input 2
1 1 1 8
6 2 7 3
8 4 6
2 6 10
4 2 9
5 6 9
7 6 3
4 5 1
4 3 6
8 6 7
1 4 6
3 8 1
2 1 3
Sample Output 2
Sample Input 3
1 5 7 1 5 6 8
4 1 8 10 8 8 4 3 3
9 2 9
4 7 10
4 8 8
13 8 1
11 7 5
16 6 7
14 7 9
4 2 10
11 8 8
15 4 9
1 10 3
1 12 3
2 1 7
5 4 3
2 15 3
3 4 6
16 9 4
2 12 6
3 10 6
2 14 5
14 16 10
8 5 9
8 12 9
2 16 7
15 6 2
9 15 7
2 6 3
14 15 5
7 3 8
15 12 3
12 6 4
12 7 8
2 8 1
1 7 4
4 13 9
13 7 4
8 6 9
16 5 8
1 6 6
10 14 3
8 16 6
14 3 4
3 11 6
14 6 6
2 11 9
12 10 5
13 11 5
16 7 3
6 9 10
1 13 8
1 3 4
9 5 5
10 6 2
13 12 2
11 14 10
4 14 5
15 5 9
8 7 1
Sample Output 3
Hints
Problem Source
IOICamp 2020 Day3 pE
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資 | 0 |
| 2 | 0~109 | 無額外限制 | 100 |