Submission #31709235

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import deque
import heapq
# 入力
n, m, k, s = map(int, input().split())
p, q = map(int, input().split())
c = [0] * k
for i in range(k):
    c[i] = int(input()) - 1
e = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    e[a - 1].append(b - 1)
    e[b - 1].append(a - 1)
# 幅優先探索 (危険な町の判定)
dist = [10 ** 9] * n
que = deque()
for c_i in c:
    dist[c_i] = 0
    que.append(c_i)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

from collections import deque
import heapq

# 入力
n, m, k, s = map(int, input().split())
p, q = map(int, input().split())
c = [0] * k
for i in range(k):
    c[i] = int(input()) - 1
e = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    e[a - 1].append(b - 1)
    e[b - 1].append(a - 1)

# 幅優先探索 (危険な町の判定)
dist = [10 ** 9] * n
que = deque()
for c_i in c:
    dist[c_i] = 0
    que.append(c_i)
while len(que) != 0:
    v = que.popleft()
    for u in e[v]:
        if dist[u] == 10 ** 9:
            dist[u] = dist[v] + 1
            que.append(u)

# ダイクストラ法
cost = [10 ** 18] * n
que = []
cost[0] = 0
heapq.heappush(que, [0, 0])
while len(que) != 0:
    d, v = heapq.heappop(que)
    if cost[v] != d:
        continue
    for u in e[v]:
        if dist[u] == 0:
            continue
        if dist[u] <= s:
            c = q
        else:
            c = p
        if cost[u] > d + c:
            cost[u] = d + c
            heapq.heappush(que, [d + c, u])
if dist[n - 1] <= s:
    print(cost[n - 1] - q)
else:
    print(cost[n - 1] - p)

Submission Info

Judge Result