Skip to content

1193: 安慰奶牛

题目

题目描述

约翰有$N$个牧场,编号依次为$1$到$N$。每个牧场里住着一头奶牛。连接这些牧场的有$P$条道路,每条道路都是双向的。第$j$条道路连接的是牧场$S_j$和$E_j$,通行需要$L_j$的时间。两牧场之间最多只有一条道路。约翰打算在保持各牧场连通的情况下去掉尽量多的道路。

约翰知道,在道路被强拆后,奶牛会非常伤心,所以他计划拆除道路之后就去忽悠她们。约翰可以选择从任意一个牧场出发开始他的维稳工作。当他走访完所有的奶牛之后,还要回到他的出发地。每次路过牧场$i$的时候,他必须花$C_i$的时间和奶牛交谈,即使之前已经做过工作了,也要留下来再谈一次。注意约翰在出发和回去的时候,都要和出发地的奶牛谈一次话。请你计算一下,约翰要拆除哪些道路,才能让忽悠奶牛的时间变得最少?

输入格式

第 $1$ 行: 用空格隔开的两个整数$N$和$P$

第 $2\cdots N+1$ 行: 第$i+1$行包含了一个整数: $C_i$

第 $N+2\cdots N+P+1$ 行: 第 $N+j+1$ 行包含用空格隔开的三个整数: $S_j, E_j$ 和 $L_j$

输出格式

输出一行一个整数,表示所需要的总时间(包含和在你所在的牧场的奶牛的两次谈话时间)。

样例输入

5 7

10

10

20

6

30

1 2 5

2 3 5

2 4 12

3 4 17

2 5 15

3 5 6

4 5 12

样例输出

176

Hint

``` +-(15)-+ / \ / \ 1-(5)-2-(5)-3-(6)--5 \ /(17) / (12)\ / /(12) 4------+

Keep these paths: 1-(5)-2-(5)-3 5 \ / (12)\ /(12) *4------+ ```

数据范围

对于 $100\%$的数据,$5\le N \le 10000,N-1 \le P \le 100000,1\le L_i,C_i \le 1000$。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!