大力水手问禅师:“大师,很多事情都需要用很大力气才能完成,而我在吃了菠菜之后力气很大,于是就导致我现在非常依赖菠菜。我很讨厌我的现状,有没有办法少吃点菠菜甚至不吃菠菜却仍很有力气?”
禅师浅笑,答:“方法很简单,不过若想我教你,你需先下山徒手修路。”
山下是
现在大力水手要根据禅师的意思在村庄间修路。禅师规定大力水手需要在
- 第
天,禅师指定了两个村庄 和 ,在草图上 号村庄到 号村庄的最短路径上的所有村庄(包括 和 )中,大力水手需要选出若干对村庄(一个村庄可以被重复选多次,当然大力水手在这天也可以一对村庄都不选),然后在选出的每一对村庄间修建双向道路。 - 在实地考察中大力水手发现,有
个限制关系 ,表示在第 天无法在 号村庄到 号村庄间修路(路是双向的,所以自然也无法在 号村庄到 号村庄间修路)。 - 每一天都有个修理所需力气值
,表示在第 天每修建一条道路都要耗费 点力气值。
大力水手开始蛮力干了起来,一罐又一罐地吞食菠菜,结果经常修建一些无用的道路,每天都累得筋疲力尽。
作为一个旁观者,请你帮大力水手求出要想让
输入格式
第一行三个非负整数
接下来一行
接下来
接下来
输出格式
输出一行一个整数,表示所需要的最小总力气值。保证至少存在一种修路的方法使得任意一对村庄之间都可以互相到达。
C/C++ 输入输出 long long 时请用 %lld
。C++ 可以直接使用 cin/cout 输入输出。
样例一
input
5 2 3 1 1 3 3 2 4 1 5 4 2 1 3 2 1 3 1 1 3 4
output
6
explanation
第一天大力水手本来可以在
一种可能的最优方案是,第一天大力水手在
样例二
见样例数据下载。这个样例中
样例三
见样例数据下载。
限制与约定
测试点编号 | 其他 | |||
---|---|---|---|---|
1 | 无 | |||
2 | 无 | |||
3 | ||||
4 | ||||
5 | 保证对于 | |||
6 | ||||
7 | 无 | |||
8 | ||||
9 | ||||
10 |
时间限制:
空间限制:
后记
由于你的帮助,大力水手顺利修完了道路而且使用的力气值是原定计划的 0.01%。
大力水手对禅师说:“我明白了!我以前都是在使用蛮力,从今往后我要多思索,多使用巧力解决问题。”
禅师摆摆手,嘿嘿一笑:“对不起,我只是想请你帮忙修路而已。”
大力水手吃了一罐菠菜,把禅师打死了。