이번 문제는 다익스트라 알고리즘을 통해 해결하였다. 우선 점령된 도시와 거리가 s 이하인 도시를 찾아내는 get_costs()함수를 구현하였다. 모든 도시의 숙박 비용을 p로 두고, 점령된 도시에서 BFS를 통해 옆 도시로 이동하며 거리를 카운트하고, s이내라면 비용을 q로 갱신해주었다. 이 과정이 끝나면 다익스트라 알고리즘을 통해 도시를 이동한다. 이때 점령된 도시는 방문할 수 없으므로 이를 예외 처리 해야한다. 첫 도시와 끝 도시에서는 숙박하지 않으므로 두 도시의 비용은 0으로 갱신해두었다.

42%에서 계속 에러가 나서 코드를 여러번 고쳐보았지만, 해결되지 않았고, 문제에서 n의 최댓값 100000, p, q의 최댓값 100000가 모두 적용되었을 때 비용이 1e10이 나오는데, 초기에 다익스트라에 사용된 costs함수의 초깃값을 1e9로 해놓아 오답처리 된 것이라는 것을 찾아냈다. 그래서 sys라이브러리를 통해 sys.maxsize로 초깃값을 선언하여 해결하였다.

Code

import sys
import heapq
from collections import deque
n, m, k, s = map(int, input().split())
p, q = map(int, input().split())
infested = [int(input()) for _ in range(k)]
road = [[] for _ in range(n+1)]
pay = [p for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    road[a].append(b)
    road[b].append(a)
def get_costs(cur, dist):
    q = deque()
    q.append((cur, dist))
    result = []
    visited[cur] = True
    while q:
        cur, dist = q.popleft()
        if dist > s:
            continue
        else:
            result.append(cur)
        for nxt in road[cur]:
            if not visited[nxt]:
                visited[nxt] = True
                q.append((nxt, dist+1))
    return result
def get_min_cost():
    hq = []
    heapq.heappush(hq, (0, 1))
    costs = [sys.maxsize for _ in range(n+1)]
    costs[1] = 0
    while hq:
        cost, cur = heapq.heappop(hq)
        if cost > costs[cur]:
            continue
        for nxt in road[cur]:
            nxt_cost = cost+pay[nxt]
            if nxt in set(infested):
                continue
            if costs[nxt] > nxt_cost:
                costs[nxt] = nxt_cost
                heapq.heappush(hq, (nxt_cost, nxt))
    return costs[n]
for cur in infested:
    visited = [False for _ in range(n+1)]
    tmp = get_costs(cur, 0)
    for land in tmp:
        pay[land] = q
    pay[0], pay[n] = 0, 0
print(get_min_cost())