E-孤岛求生

题目描述

由于飞机事故，小青落入了一座神秘孤岛，里面竟然有僵尸。

岛上共有 $N$ 个城镇，从 $1$ 到 $N$ 编号，这些城镇通过 $M$ 条道路相互连接。每条道路都连接两个不同的城镇。小青 君可以在这些道路上自由往返，但不能随意穿越道路以外的地方。

孤岛中有一些城镇被僵尸占领，无法靠近。从被僵尸占领的城镇，通过不超过 $S$ 条道路可以到达的城镇称为“危险城镇”，其余的称为“安全城镇”。

小青的将落地在城镇 $1$，而安全避难所位于城镇 $N$。这两个城镇都没有被僵尸占领。由于每次在城镇之间移动需要时间，小青必须在每个目的地城镇过夜。在“安全城镇”过夜的费用较低，仅为 $P$ 元，而在“危险城镇”过夜的费用较高，为 $Q$ 元。小青的目标是以最低的住宿费用从城镇 $1$ 到达城镇 $N$。在城镇 $1$ 和城镇 $N$ 无需过夜。

请计算小青从将落地到安全避难所所需的最少住宿费用。

输入格式

输入第 $1$ 行包含四个整数 $N,\ M,\ K,\ S$，分别表示 $N$ 个城镇，$M$ 条道路，$K$ 个被僵尸占领的城镇，以及“危险城镇”的距离界限 $S$。 ($2 \leq N \leq 10^5，$1 \leq M \leq 2\times 10^5$，$0 \leq K \leq N - 2$，$0 \leq S \leq 10^5$)

第 $2$ 行包含两个整数 $P, Q$，分别表示在“安全城镇”的过夜费用和在“危险城镇”的过夜费用。 ($1 \leq P < Q \leq 10^5$)

接下来的 $K$ 行，每行一个整数 $C_i$，表示被僵尸占领的城镇编号。 ($2 \leq C_i \leq N - 1$)

接下来的 $M$ 行：每行两个整数 $A_j, B_j$，表示存在一条连接城镇 $A_j$ 和 $B_j$ 的道路。($1 \leq A_j < B_j \leq N$)

输入数据保证从城镇 $1$ 可以通过未被僵尸占领的城镇路径到达城镇 $N$。

输出格式

输出 小青从城镇 $1$ 到城镇 $N$ 最低住宿费用的总和。

请注意，输出结果可能超出 $32$ 位有符号整数的范围。

样例解释

以下示例如图所示，圆圈代表城镇，线条代表道路：

在此图中，城镇 $3$，$4$，$6$，$8$ 和 $12$ 被视为“危险城镇”。以下路径可使住宿费用最低：

• 从城镇 $1$ 到城镇 $2$，在城镇 $2$ 花费 $1,000$ 元。
• 从城镇 $2$ 到城镇 $5$，在城镇 $5$ 花费 $1,000$ 元。
• ...（依此类推）

按照这样的步骤，小青花费总计为 $11,000$ 元，因此输出 $11,000$。

样例输入 1

13 21 1 1
1000 6000
7
1 2
3 7
2 4
5 8
8 9
2 5
3 4
4 7
9 10
10 11
5 9
7 12
3 6
4 5
1 3
11 12
6 7
8 11
6 13
7 8
12 13

样例输出 1

11000

样例输入 2

21 26 2 2
1000 2000
5
16
1 2
1 3
1 10
2 5
3 4
4 6
5 8
6 7
7 9
8 10
9 10
9 11
11 13
12 13
12 15
13 14
13 16
14 17
15 16
15 18
16 17
16 19
17 20
18 19
19 20
19 21

样例输出 2

15000