#P18859. [Croatian CPC2025] Guba Graf
[Croatian CPC2025] Guba Graf
Guba Graf
题目描述
一座城市由一张有 个顶点、 条边的连通无向带权图表示。有 名参赛者,他们的起点分别为 。
组织者要在图中选择一个简单环。这里的简单环由至少三个互不相同的顶点 构成,且 与 之间有边,其中 。
每位参赛者需要先到达这个环,然后沿环完整跑一圈,回到自己第一次到达的环上顶点。最先完成的参赛者获胜。
环上的边会铺设特殊路面:经过环上边的每一个单位长度需要 秒,经过其他边的每一个单位长度需要 秒。所有参赛者的速度规则相同。
组织者可以自行选择环。求获胜者完成比赛所需的最少时间。
输入格式
第一行包含整数 。
第二行包含 个整数 。
接下来 行,每行包含整数 ,表示顶点 之间有一条长度为 的无向边。
输出格式
输出一个整数,表示最少时间。
数据范围
- ,,。
- ,。
- 所有顶点编号均在 到 之间。
- 图连通,不含自环和重边。
样例 1
输入
8 12 3 1 2
4 2 7
1 5 2
7 5 12
2 7 2
7 3 22
8 1 14
2 3 40
4 6 4
1 6 4
2 4 20
8 6 16
7 8 20
5 8 10
输出
40
样例 2
输入
3 3 1 10 5
2
1 2 22
2 3 24
3 1 26
输出
720