문제
정올이는 정보과학 교육과 관련된 세미나에 초대를 받아 참석하려고 한다.
세미나가 열리는 도시에 가기 위해서는 여러 도시를 거쳐서 이동할 수 있으며
도시간 이동하기 위한 교통수단은 초고속열차, 렌트카, 자전거를 이용하는 3가지 방법이 있다.
정올이는 늘 접이식 자전거를 들고 다니기 때문에 자전거로 이동하는 데에는 비용이 발생하지 않는다.
접이식 자전거는 당연히 열차와 렌트카에도 싣고 탈 수 있다.
정올이가 이용하는 렌트카 회사는 여러 도시에 지점이 있어서 지점이 있는 도시에서는 어디에서든 빌릴 수도 있고 반납할 수도 있다.
자전거를 제외한 교통수단에 따른 비용은 단위 거리당 금액으로 정해진다.
모든 연결된 도로에는 렌트카 및 자전거로 이동하는 것은 물론 초고속열차도 운행하고 있어서 모두 이용이 가능하다.
세미나가 열리는 도시에는 세미나를 시작하는 시간까지만 도착하면 된다.
물론 렌트카를 사용하고 있다면 세미나장이 있는 도시에 렌트가 지점이 있거나 없다면 도착하기 전에 반납되어야 한다.
각 도시 및 교통수단에 관한 정보가 주어질 때 정올이가 세미나 시작시간까지 세미나 개최 도시에 도착하기 위한 최소비용을 구하는 프로그램을 작성하라.
입력
입력의 첫 번째 줄에는 도시의 수 N과 간선(도로)의 수 M, 세미나 개최까지 남은시간 T, 렌트카 지점의 수 L이 차례로 주어진다. 도시의 번호는 1부터 N까지 부여되고 정올이가 출발하는 도시는 1번이며 세미나가 개최되는 도시는 N번이다.
(2<= N <= 100, N <= M <= N * (N - 1) / 2, 2 <= T <= 1000, 1 <= L <= N))
두 번째 줄부터 M줄에 걸쳐 3개의 정수 s, e, d가 주어지는데 이는 s 도시와 e 도시 사이의 거리가 d임을 나타낸다. 도로간 양방향 통행이 가능하다.
(1 <= s, e <= N, 1 <= d <= 20)
다음 줄에는 렌트카 지점이 있는 도시의 번호 L개가 공백으로 구분하여 주어진다.
다음줄에는 자전거, 렌트카, 고속열차 순으로 단위 거리를 이동하는데 걸리는 시간이 차례대로 주어진다. (30 >= 자전거 > 렌트카 > 고속열차 >= 1)
마지막 줄에는 렌트카와 고속열차의 순서대로 단위 거리를 이동하는데 드는 비용이 주어진다. 자전거는 비용이 발생하지 않으므로 입력되지 않는다.
(1 <= 렌트카 < 고속열차 <=3000)
출력
정올이가 세미나 시작시간까지 도착하기 위한 최소비용을 출력한다.
예제
4 6 99 2
1 2 3
1 3 4
1 4 7
2 3 3
2 4 5
3 4 2
2 3
30 10 3
200 1000
3600
힌트
출처
jungol
로그인해야 코드를 작성할 수 있어요.