填空题

地铁打卡活动

Question

地铁迷在某个城市组织了地铁打卡活动。活动要求前往该城市中的所有地铁站进行打卡。打卡可以在站外或者站内进行。地铁的计价规则如下：只要不出站，就不计费；出站时，只计算进站和出站站点的距离。如在同一个站点进出站，按照最低票价 a 元计算。假设地铁票不会超时。大部分站点都是通过地铁线连通的，而且地铁站的连通是双向的（若 A，B 连通，则 B，A连通），且具有传递性的（若 A，B 连通，且 B，C 连通，则 A，C连通）。但并不是所有的地铁站都相互连通，在不能通过坐地铁达到的两个地点间，交通的花费则提高到 b 元。地铁迷从酒店起点出发，再回到酒店。假设从酒店到达任意地铁站的交通花费为 b 元。请计算地铁迷完成打卡最小交通花费。

输入描述： 每组输入包括m + 1行。

第1行包含4个整数n，m，a，b，其中n表示地铁站点数，m表示连通的地铁站点对数，a代表地铁最低票价，b代表非地铁方式票价，其中0 < a < b。

第2到m + 1行，每行2个整数Hi，Ti代表站点Hi和Ti站点是连通的（0 <= i< m）。输入样例： 8 7 3 6 0 1 1 2 2 3 0 3 4 5 5 6 4 7 输出描述： 输出只有一行，包含一个整数，表示打卡的最小交通花费。输出样例 24