#P18859. [Croatian CPC2025] Guba Graf

[Croatian CPC2025] Guba Graf

Guba Graf

题目描述

一座城市由一张有 NN 个顶点、MM 条边的连通无向带权图表示。有 KK 名参赛者,他们的起点分别为 s1,…,sKs_1,\ldots,s_K。

组织者要在图中选择一个简单环。这里的简单环由至少三个互不相同的顶点 x1,…,xcx_1,\ldots,x_c 构成,且 xix_i 与 xi+1x_{i+1} 之间有边,其中 xc+1=x1x_{c+1}=x_1。

每位参赛者需要先到达这个环,然后沿环完整跑一圈,回到自己第一次到达的环上顶点。最先完成的参赛者获胜。

环上的边会铺设特殊路面:经过环上边的每一个单位长度需要 AA 秒,经过其他边的每一个单位长度需要 BB 秒。所有参赛者的速度规则相同。

组织者可以自行选择环。求获胜者完成比赛所需的最少时间。

输入格式

第一行包含整数 N,M,K,A,BN,M,K,A,B。

第二行包含 KK 个整数 s1,…,sKs_1,\ldots,s_K。

接下来 MM 行,每行包含整数 ui,vi,wiu_i,v_i,w_i,表示顶点 ui,viu_i,v_i 之间有一条长度为 wiw_i 的无向边。

输出格式

输出一个整数,表示最少时间。

数据范围

  • 1≤N≤5001\le N\le500,1≤M≤N(N−1)/21\le M\le N(N-1)/2,1≤K≤N1\le K\le N。
  • 0≤A,B≤1060\le A,B\le10^6,1≤wi≤1091\le w_i\le10^9。
  • 所有顶点编号均在 11 到 NN 之间。
  • 图连通,不含自环和重边。

样例 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