====== 국왕의 방문 ======

===== 풀이 =====
  * 발상:★★, 구현:★★
  * 우선 문제 이해에 좀 시간이 걸렸다. 기본적으로는 최단 경로 문제이긴 한데, 특정 시간에는 특정 엣지를 이용할수 없다는 제약이 들어간다.
  * 제약을 바꿔서 생각하면, 엣지를 사용할수 없는 시간에는 엣지가 사용가능해질때까지 기다렸다가 이동을 하게 되므로, 그냥 엣지의 웨이트가 더 증가한다고 생각할수 있다. 그러면, 엣지의 코스트가 엣지의 시작 노드까지 도달하는데에 사용된 코스트에 따라 바뀌는 문제라고 생각할 수 있다.
  * 다행히도, u->v 엣지를 지나갈 때 엣지의 코스트가 바뀌더라도, u에 가장 빨리 도달했을때가 v에도 가장 빨리 도달하게 된다. 따라서 다익스트라 알고리즘을 사용해서 최단 경로를 구할 수 있다. ([[ps:단일_출발지_최단_경로#엣지_웨이트가_동적으로_변할때|다익스트라]] 참고)
  * 이제 저렇게 엣지의 코스트가 바뀌는 것을 고려해서 다익스트라를 구현하면 된다. 시간복잡도는 O(ElogV). teflib.tgraph.dijkstra를 그대로 사용할수는 없어서, 로직을 수정해서 새로 짰다.
  * 국왕이 지나가는 엣지들에 대해서 사용불가능한 시간 범위을 계산해서 저장해주어야 한다. 이때, 시간 범위의 시작을 -K로 하면, 비교할때 좀더 간단하다.


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 2982. 국왕의 방문".

- Problem link: https://www.acmicpc.net/problem/2982
- Solution link: http://www.teferi.net/ps/problems/boj/2982

Tags: [Dijkstra]
"""

import heapq
import itertools
import sys

INF = float('inf')


def dijkstra(wgraph, blocked_period, source, dest):
    distances = [INF] * len(wgraph)
    distances[source] = 0
    heap = [(0, source)]
    while heap:
        dist_u, u = heapq.heappop(heap)
        if dist_u != distances[u]:
            continue
        if u == dest:
            return dist_u
        for v, dist_uv in wgraph[u].items():
            if ((period := blocked_period.get((u, v))) and
                    period[0] <= dist_u < period[1]):
                dist_v = period[1] + dist_uv
            else:
                dist_v = dist_u + dist_uv
            if dist_v < distances[v]:
                distances[v] = dist_v
                heapq.heappush(heap, (dist_v, v))


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    wgraph = [{} for _ in range(N)]
    # pylint: disable=unused-variable
    A, B, K, G = [int(x) for x in sys.stdin.readline().split()]
    route = [int(x) for x in sys.stdin.readline().split()]
    for _ in range(M):
        U, V, L = [int(x) for x in sys.stdin.readline().split()]
        wgraph[U - 1][V - 1] = wgraph[V - 1][U - 1] = L

    blocked_period = {}
    beg = -K
    for u, v in itertools.pairwise(route):
        end = beg + wgraph[u - 1][v - 1]
        blocked_period[u - 1, v - 1] = blocked_period[v - 1, u - 1] = (beg, end)
        beg = end

    print(dijkstra(wgraph, blocked_period, A - 1, B - 1))


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_2}}