문제
진흥국에는 N개의 여행지가 있다.
각 여행사에서는 여행지 사이를 순회하는 셔틀버스를 운행하고 있다.
자유 관광을 하는 K명의 여행자들이 각각 현재 여행지에서 마지막으로 다른 여행지로 이동을 했다가 공항이 있는 N번 여행지로 이동하려고 한다.
그런데 이번이 마지막 여행지라서 반드시 기념품을 파는 가게를 한 곳이라도 들려야 한다.
여행지에는 기념품을 파는 가게가 있지만 모든 여행지마다 가게가 있는 것은 아니다.
공항이 있는 N번 여행지에도 기념품 가게가 있을 수도 있고 없을 수도 있다.
여행지 사이의 정보와 기념품 가게가 있는 여행지가 주어질 때 각 여행자들이 마지막 여행을 마치고 N번 여행지로 이동하기 위해서 지불해야 하는 최소비용을 구하는 프로그램을 작성하라.
입력
첫 번째 줄에 여행지의 수 N(5 <= N <= 200), 경로의 수 M(N – 1 <= M <= N * (N – 1) / 2), 기념품 가게가 있는 여행지의 수 L(1 <= L <= N), 여행자의 수 K(1 <= K <= 10,000)가 공백으로 구분하여 입력된다.
두 번째 줄에는 기념품 가게가 있는 여행지의 번호 L개가 공백으로 구분되어 차례대로 입력된다.
세 번째 줄부터 M개의 줄에는 각각 세 개의 정수 Xi, Yi, Vi가 입력된다. Xi에서 Yi로 이동하는데 드는 비용이 Vi임을 나타낸다. (단방향으로 Yi에서 Xi로 이동하는 것은 안된다.)
다음 줄부터 K개의 줄에는 두 개의 정수 Si, Ei가 입력된다. 각 여행자의 현재 위치와 목적지를 나타낸다.
출력
K개의 줄에 걸쳐 각 여행자가 지불해야 하는 비용을 출력한다.
만약 여행이 불가능한 경우에는 –1을 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 10점 | N ≤ 10 |
| #2 | 15점 | L = N |
| #3 | 20점 | L = 1 |
| #4 | 55점 | 추가적인 제한이 없음. |
예제
3 4 1 3
1
3 1 9
1 2 7
2 3 3
3 2 10
1 2
2 3
3 2
10
22
19
로그인해야 코드를 작성할 수 있어요.