#P10731. [2020年省队模拟]最短路

    ID: 9849 传统题 1000ms 888MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-广度优先搜索链表时间戳避免清空数组

[2020年省队模拟]最短路

题目描述

给定一张有 nn 个点、mm 条白边的无向连通图。对每一对不同的点,如果它们在原图中最少经过两条边才能互相到达,就在它们之间添加一条黑边。判断是否添加黑边时,只考虑原图的白边。

在新图中,每条白边的权值为 aa,每条黑边的权值为 bb。求从 11 号点到其余各点的最短路长度。

输入格式

第一行四个整数 n,m,a,bn,m,a,b。

接下来 mm 行,每行两个整数 x,yx,y,表示一条连接 xx 与 yy 的白边。

输出格式

输出 n−1n-1 行。第 ii 行表示新图中从 11 号点到 i+1i+1 号点的最短路长度。

样例

5 5 3 2
1 2
2 3
3 4
4 5
3 1
3
3
2
5

数据范围

1≤n≤1.5×1051\le n\le1.5\times10^5,n−1≤m≤3×105n-1\le m\le3\times10^5,0≤a,b≤1090\le a,b\le10^9。原赛题面保证无重边和自环。现有评测的部分输入含自环,读到后可忽略。因为边权非负,且自环不影响不同顶点之间的原图距离,它不会影响答案。

原赛子任务 特殊限制 原赛分值
1 m≤1000m\le1000 15
2 原图是一棵树
3 m≤5×104m\le5\times10^4 25
4 b=0b=0 20
5 无特殊限制 25

原 PDF 题面