2324 . 送外賣

Submit out of contest
Status
Discussion / Solution
Back to Problems List

Description

外賣，我們今天來送外賣～
總共有 $n$ 個城市，但是每個城市互不相連，怎麼送呢？

我們可以花費 $W(i,j)$ 的價錢在城市 $i$ 和城市 $j$（$1\leq i,j\leq n,i\neq j$）之間蓋一條雙向道路，$W(i,j)$ 計算方式如下：

  • 有一棵 $n$ 個節點的樹 $T$，有編號 $1\sim n-1$ 的邊，每條邊可以表示成 $(u_i,v_i,w_i)$，代表 $u_i,v_i$ 兩個節點以一條邊權為 $w_i$ 的邊相連。
  • $W(i,j)=D(i,j)+a_i+a_j$，$D(i,j)$ 為在 $T$ 上節點 $i$ 和節點 $j$ 最短路徑長，$a_i,a_j$ 則為兩個城市的發達程度。
  • $a_1\sim a_n$ 和 $T$ 在初始時會提供。

為了能在 $n$ 個城市都送到外賣，我們必須要讓任兩個相異的城市間都至少有一個由若干條道路組成的路徑相連。
為了把錢存下來買更有用的東西，我們想使蓋道路的錢越少越好，請問最少可以是多少？

Input Format

第一行有一個正整數 $n$，代表城市數量。
第二行有 $n$ 個正整數 $a_1\sim a_n$，代表每個城市的發達程度。
接下來 $n-1$ 行，第 $i$ 行會輸入三個正整數 $u_i,v_i,w_i$，代表 $T$ 上的第 $i$ 條邊。

對於所有測試資料：

  • $2\leq n\leq 2\times 10^ 5$
  • $1\leq a_i\leq 10^ 9$
  • $1\leq u_i,v_i\leq n$
  • $1\leq w_i\leq 10^ 9$
  • 保證 $T$ 是一棵樹

Output Format

輸出一個整數代表蓋道路最少要花多少錢。

Sample Input 1

4
1 3 5 1
1 2 1
2 3 2
3 4 3

Sample Output 1

22

Hints

在範測一中：在 $(1,2),(1,4),(3,4)$ 蓋道路總花費最少，為 $W(1,2)+W(1,4)+W(3,4)=5+8+9=22$。

Problem Source

Atcoder Code Festival 2017 Final J

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~15 $n\leq 1000$ 19
3 1, 16~22 $u_i=1,v_i=i+1$ 19
4 0~1, 23~28 $u_i=i,v_i=i+1$ 29
5 0~54 無其他限制 33

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 524288 65536 1 2 4 5
1 4000 524288 65536 2 3 4 5
2 4000 524288 65536 2 5
3 4000 524288 65536 2 5
4 4000 524288 65536 2 5
5 4000 524288 65536 2 5
6 4000 524288 65536 2 5
7 4000 524288 65536 2 5
8 4000 524288 65536 2 5
9 4000 524288 65536 2 5
10 4000 524288 65536 2 5
11 4000 524288 65536 2 5
12 4000 524288 65536 2 5
13 4000 524288 65536 2 5
14 4000 524288 65536 2 5
15 4000 524288 65536 2 5
16 4000 524288 65536 3 5
17 4000 524288 65536 3 5
18 4000 524288 65536 3 5
19 4000 524288 65536 3 5
20 4000 524288 65536 3 5
21 4000 524288 65536 3 5
22 4000 524288 65536 3 5
23 4000 524288 65536 4 5
24 4000 524288 65536 4 5
25 4000 524288 65536 4 5
26 4000 524288 65536 4 5
27 4000 524288 65536 4 5
28 4000 524288 65536 4 5
29 4000 524288 65536 5
30 4000 524288 65536 5
31 4000 524288 65536 5
32 4000 524288 65536 5
33 4000 524288 65536 5
34 4000 524288 65536 5
35 4000 524288 65536 5
36 4000 524288 65536 5
37 4000 524288 65536 5
38 4000 524288 65536 5
39 4000 524288 65536 5
40 4000 524288 65536 5
41 4000 524288 65536 5
42 4000 524288 65536 5
43 4000 524288 65536 5
44 4000 524288 65536 5
45 4000 524288 65536 5
46 4000 524288 65536 5
47 4000 524288 65536 5
48 4000 524288 65536 5
49 4000 524288 65536 5
50 4000 524288 65536 5
51 4000 524288 65536 5
52 4000 524288 65536 5
53 4000 524288 65536 5
54 4000 524288 65536 5
Submit out of contest
Back to Top