← 返回题目列表

AtCoder · joi2016yo_e

E. 僵尸岛

中文机器翻译题面 查看原题

配点: 100 点

問題

JOI 你居住的岛屿已被僵尸入侵。 JOI 你决定逃到岛上最安全的避难所。

JOI 你居住的岛屿是一个小镇 1 卡拉町 至 N 它由 N 个城镇组成,各城镇之间有道路相连。在岛上 M 书里有路,每条路都不一样 2 它连接两个城镇。 JOI 道路上可以双向自由移动,但不能通过道路以外的道路从一个城镇前往另一个城镇。

一些城镇被僵尸控制,无法访问。来自僵尸统治的小镇 S 使用少于一条道路即可到达的城镇称为危险城镇。其他城镇称为非危险城镇。

JOI 你的家就是城镇 1 ,避难所位于镇内。 它位于 N 。镇 1,町 N 不受僵尸控制。由于在岛上的道路上行驶需要时间,JOI每次从一个城镇搬到另一个城镇时都必须在目的地城镇过夜。如果JOI住在非危险城镇,住宿费会很低。 P 住便宜的酒店,但如果住在危险的城镇,最好有良好的保安服务。 Q 入住日元的豪华旅馆。 JOI 你搬家是为了尽可能降低住宿费用,并且 我想撤离直到 N 。镇 1 山地 N 无需过夜。

JOI 君美镇 求前往 1 卡拉町 至 N 所需的最低住宿总费用。 在


入力

输入是 2 + K + M 行组成。

1 行中,4 整数 N, M, K, S (2 \leqq N \leqq 100\,000,1 \leqq M \leqq 200\,000,0 \leqq K \leqq N - 2,0 \leqq S \leqq 100\,000)以空格作为分隔符。这意味着该岛 N 城镇和 M 由道路组成,N 城镇 K 城镇被僵尸控制,并且来自被僵尸控制的城镇 S 这意味着使用少于一条道路即可到达的城镇称为危险城镇。

2 行中,2 整数 P, Q (1 \leqq P < Q \leqq 100\,000)以空格作为分隔符。这意味着在JOI没有危险的小镇,住宿费用很低。 P 我们住的是日元旅馆,在危险的小镇,住宿费很低。 Q 代表入住日元酒店。

继续 一个整数,表示第 K 行 i 行目 (1 \leqq i \leqq K) 是一个整数 C_i (2 \leqq C_i \leqq N - 1)被写入。这是一个小镇 C_i 表示它被僵尸控制。C_1, \ldots, C_K 都是不同的。

继续 一个整数,表示第 M 行 j 行目 (1 \leqq j \leqq M)有2 整数 A_j, B_j (1 \leqq A_j < B_j \leqq N)以空格作为分隔符。这是一个小镇 A_j 和镇 表示 B_j 之间有一条路。一样 集合 (A_j, B_j) 是 它从未被写入超过 2 次。

在给定的输入数据中,该镇 保证你只能在 1 卡拉町 至 N 之前穿过未被僵尸占领的城镇。

出力

JOI 君美镇 1 卡拉町 至 N 旅行时所需的最低住宿费用总额 1 行。

输出是 32 请注意,它不一定落在有符号整数的范围内。


入力例 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

入出力例 1 对应下图。圆圈代表城镇,线条代表道路。

在这种情况下,该镇 3,町 4,町 6,町 8,町 12 是一个危险的城镇。

您可以通过按以下顺序在城镇之间移动来最大限度地减少总住宿费用。 转至

  • 町 1 卡拉町 至 2 。镇 住宿费用为 2 住宿费为 1\,000 住在便宜的酒店。
  • 町 2 卡拉町 至 5 。镇 住宿费用为 5 住宿费为 1\,000 住在便宜的酒店。
  • 町 5 卡拉町 至 9 。镇 住宿费用为 9 住宿费为 1\,000 住在便宜的酒店。
  • 町 9 卡拉町 至 10 。镇 住宿费用为 10 住宿费为 1\,000 住在便宜的酒店。
  • 町 10 卡拉町 至 11 。镇 住宿费用为 11 住宿费为 1\,000 住在便宜的酒店。
  • 町 11 卡拉町 至 12 。镇 住宿费用为 12 住宿费为 6\,000 入住日元的豪华旅馆。 我不会住在
  • 町 12 卡拉町 至 13 。镇 住宿费用为 13 。

JOI 当您乘坐此路线旅行时,总住宿费用为 11\,000 由于变成日元, 输出11\,000 。


入力例 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