打击罪犯
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
背景
在 \(3030\) 年,C 城治安还是很差。
描述
C 城有 \(N\) 个走私非法物品的团伙,它们之间有密切的交易,他们之间的关系可以看成是一个无向图,每一个团伙可以看成一个节点,两个团伙有交易当且仅当其存在一条路径连接这两个节点。而两个节点之间存在一条长度为 \(x\) 的边则意味着这两个团伙有一条长度为 \(x\) 的商道。
现在的 C 城警局局长小 Z 了解到**所有的团伙都是存在交易的**(即整个图是联通的)。他的任务是:将罪犯团伙打的尽量分散。
小 Z 认为假如一个点被摧毁后使得某些点无法交易,则这个点是值得摧毁的。他希望摧毁所有值得摧毁的点。
摧毁节点的办法是安放一个炸弹,这个过程需要 \(1\) 单位时间,由于技术落后,小 Z 只能步行。我们假定小 Z 可以分身(~~当局长真是可惜了~~),所以说,您只需要帮小 Z 找到一些路径,使得所有值得摧毁的点联通,这样小 Z 花费的时间就是路径权值之和 \(+\) 摧毁节点的时间了。
时间就是金钱,小 Z 希望您找到一些路径,在满足上述条件的情况下时间尽可能少。
格式
输入格式
第一行是两个数 \(N\) 和 \(M\),表示节点个数和边的个数。
接下来 \(M\) 行,每行三个数 \(u_i\),\(v_i\),\(x_i\) 表示 \(u_i\) 和 \(v_i\) 间有一条长度为 \(x_i\) 的点。
输出格式
一个整数,表示最短时间。
样例
#1
3 2
1 2 233
2 3 233
输出
1
#2
6 6
1 2 1
3 4 1
5 6 1
2 4 1
4 6 1
6 2 1
输出
5
#3
10 9
1 2 1
2 3 1
2 5 1
4 5 1
5 6 1
6 7 1
5 9 1
8 9 1
9 10 1
输出
7
提示说明
样例 1 解释:
从 2 号节点出发,摧毁 2 号节点,耗时为 \(1\)。
样例 2 解释:
从 2 号节点出发,摧毁 2 号节点,再沿着 2 -> 4 的路径到达 4 号节点,摧毁 4 号节点,最后沿着 4 -> 6的路径到达 6 号节点,摧毁 6 号节点,耗时为 \(5\)
【LZR-001】LZOJ 2020 年 6 月月赛 Div.2
- 状态
- 已结束
- 规则
- OI
- 题目
- 4
- 开始于
- 2020-06-12 18:00
- 结束于
- 2020-06-13 14:00
- 持续时间
- 20.0 小时
- 主持人
- 参赛人数
- 6