국왕의 방문
시간 제한1초메모리 제한128 MB
왕의 이동으로 인해 특정 도로가 일정 시간 동안 폐쇄되는 상황에서, 배달 차량이 A에서 B까지 도달하는 최소 시간을 구하는 문제입니다.
문제
도시는 1번부터 N번까지 번호가 붙은 교차로와, 교차로를 연결하는 M개의 양방향 도로로 이루어져 있다. 각 도로를 지나가는 데 걸리는 시간은 주어지며, 국왕과 배달 차량 모두 같은 시간이 걸린다.
국왕은 시각 0에 출발해 주어진 순서대로 교차로를 방문한다. 국왕이 어떤 도로에 시각 t에 진입하고 그 도로를 지나가는 데 L분이 걸린다면, 다른 차량은 시각 t 이상 t+L 미만에는 그 도로에 진입할 수 없다. 단, 시각 t보다 먼저 그 도로에 들어간 차량은 계속 지나갈 수 있다.
배달 차량은 국왕이 출발한 뒤 K분이 지난 시각에 교차로 A에서 출발해 교차로 B까지 가야 한다. 도로 통제 때문에 기다려야 할 수도 있다. 배달 차량이 출발한 뒤 목적지에 도착하기까지 걸리는 최소 시간을 구하시오.
입력
첫째 줄에 교차로의 수 N과 도로의 수 M이 주어진다. 교차로는 1번부터 N번까지 번호가 붙어 있다. (2 <= N <= 1000, 2 <= M <= 10000)
둘째 줄에 네 정수 A, B, K, G가 주어진다. A는 배달 차량의 출발 교차로, B는 도착 교차로이다. K는 국왕이 출발한 뒤 배달 차량이 출발할 때까지의 시간 차이이고, G는 국왕이 방문하는 교차로의 개수이다. (1 <= A, B <= N, 0 <= K <= 1000, 0 <= G <= 1000)
다음에는 국왕이 방문하는 교차로 번호 G개가 순서대로 주어진다. 서로 이웃한 두 교차로 사이에는 항상 도로가 있으며, 국왕은 같은 도로를 두 번 이상 지나지 않는다.
이후 M개 줄에는 도로 정보 U, V, L이 주어진다. 이는 교차로 U와 V를 잇는 도로를 지나가는 데 L분이 걸린다는 뜻이다. L은 1 이상 1000 이하의 정수이다.
출력
배달 차량이 출발한 뒤 교차로 B에 도착하기까지 필요한 최소 시간을 분 단위로 출력한다.