250 . 產品配送問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

62.5% (5/8)

Tags

ioicamp ioicamp-2020

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

4 4 17
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

46

Sample Input 2

4 4 11
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

-1

Sample Input 3

7 9 58
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

77

Hints

Problem Source

IOICamp 2020 Day3 pE

Subtasks

No. Testdata Range Constraints Score
1 0~2 範例測資 0
2 0~109 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 500 262144 65536 1 2
1 500 262144 65536 1 2
2 500 262144 65536 1 2
3 500 262144 65536 2
4 500 262144 65536 2
5 500 262144 65536 2
6 500 262144 65536 2
7 500 262144 65536 2
8 500 262144 65536 2
9 500 262144 65536 2
10 500 262144 65536 2
11 500 262144 65536 2
12 500 262144 65536 2
13 500 262144 65536 2
14 500 262144 65536 2
15 500 262144 65536 2
16 500 262144 65536 2
17 500 262144 65536 2
18 500 262144 65536 2
19 500 262144 65536 2
20 500 262144 65536 2
21 500 262144 65536 2
22 500 262144 65536 2
23 500 262144 65536 2
24 500 262144 65536 2
25 500 262144 65536 2
26 500 262144 65536 2
27 500 262144 65536 2
28 500 262144 65536 2
29 500 262144 65536 2
30 500 262144 65536 2
31 500 262144 65536 2
32 500 262144 65536 2
33 500 262144 65536 2
34 500 262144 65536 2
35 500 262144 65536 2
36 500 262144 65536 2
37 500 262144 65536 2
38 500 262144 65536 2
39 500 262144 65536 2
40 500 262144 65536 2
41 500 262144 65536 2
42 500 262144 65536 2
43 500 262144 65536 2
44 500 262144 65536 2
45 500 262144 65536 2
46 500 262144 65536 2
47 500 262144 65536 2
48 500 262144 65536 2
49 500 262144 65536 2
50 500 262144 65536 2
51 500 262144 65536 2
52 500 262144 65536 2
53 500 262144 65536 2
54 500 262144 65536 2
55 500 262144 65536 2
56 500 262144 65536 2
57 500 262144 65536 2
58 500 262144 65536 2
59 500 262144 65536 2
60 500 262144 65536 2
61 500 262144 65536 2
62 500 262144 65536 2
63 500 262144 65536 2
64 500 262144 65536 2
65 500 262144 65536 2
66 500 262144 65536 2
67 500 262144 65536 2
68 500 262144 65536 2
69 500 262144 65536 2
70 500 262144 65536 2
71 500 262144 65536 2
72 500 262144 65536 2
73 500 262144 65536 2
74 500 262144 65536 2
75 500 262144 65536 2
76 500 262144 65536 2
77 500 262144 65536 2
78 500 262144 65536 2
79 500 262144 65536 2
80 500 262144 65536 2
81 500 262144 65536 2
82 500 262144 65536 2
83 500 262144 65536 2
84 500 262144 65536 2
85 500 262144 65536 2
86 500 262144 65536 2
87 500 262144 65536 2
88 500 262144 65536 2
89 500 262144 65536 2
90 500 262144 65536 2
91 500 262144 65536 2
92 500 262144 65536 2
93 500 262144 65536 2
94 500 262144 65536 2
95 500 262144 65536 2
96 500 262144 65536 2
97 500 262144 65536 2
98 500 262144 65536 2
99 500 262144 65536 2
100 500 262144 65536 2
101 500 262144 65536 2
102 500 262144 65536 2
103 500 262144 65536 2
104 500 262144 65536 2
105 500 262144 65536 2
106 500 262144 65536 2
107 500 262144 65536 2
108 500 262144 65536 2
109 500 262144 65536 2
Submit
Back to Top