#P10731. [2020年省队模拟]最短路
[2020年省队模拟]最短路
题目描述
给定一张有 个点、 条白边的无向连通图。对每一对不同的点,如果它们在原图中最少经过两条边才能互相到达,就在它们之间添加一条黑边。判断是否添加黑边时,只考虑原图的白边。
在新图中,每条白边的权值为 ,每条黑边的权值为 。求从 号点到其余各点的最短路长度。
输入格式
第一行四个整数 。
接下来 行,每行两个整数 ,表示一条连接 与 的白边。
输出格式
输出 行。第 行表示新图中从 号点到 号点的最短路长度。
样例
5 5 3 2
1 2
2 3
3 4
4 5
3 1
3
3
2
5
数据范围
,,。原赛题面保证无重边和自环。现有评测的部分输入含自环,读到后可忽略。因为边权非负,且自环不影响不同顶点之间的原图距离,它不会影响答案。
| 原赛子任务 | 特殊限制 | 原赛分值 |
|---|---|---|
| 1 | 15 | |
| 2 | 原图是一棵树 | |
| 3 | 25 | |
| 4 | 20 | |
| 5 | 无特殊限制 | 25 |