시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB55313910724.208%

문제

서준이는 아빠로부터 생일선물로 세계 지도를 받아서 매우 기뻤다. 세계 지도에서 최단 경로를 찾는 프로그램을 개발해서 아빠께 감사의 마음을 전달하려고 한다. 세계 지도는 도시를 정점으로 갖고 도시 간의 도로를 간선으로 갖는 무방향성 그래프이며(undirected graph), 도로의 길이가 간선의 가중치이다. 출발 정점 X에서 출발해서 P개의 중간 정점 중 적어도 한 개의 정점을 반드시 거친 후 도착 정점 Z에 도달하는 최단 거리를 구해서 우리 서준이를 도와주자.

입력

첫째 줄에 정점의 수 N (10 ≤ N ≤ 100,000), 간선의 수 M (10 ≤ M ≤ 300,000)이 주어진다.

다음 M개 줄에 간선 정보 u v w가 주어지며 도시 u와 도시 v 사이의 가중치가 정수 w인 양방향 도로를 나타낸다. (1 ≤ u, v ≤ N, uv, 1 ≤ w ≤ 1,000,000)

다음 줄에 X Z가 주어진다. (1 ≤ X, Z ≤ N, XZ)

다음 줄에 P가 주어진다. (1 ≤ PN - 3)

다음 줄에 P개의 서로 다른 중간 정점 Y (1 ≤ YN, XYZ)가 빈칸을 사이에 두고 주어진다.

출력

출발 정점 X에서 출발해서 P개의 중간 정점 중 적어도 한 개의 정점을 반드시 거친 후 도착 정점 Z에 도달하는 최단 거리를 출력한다. 도착 정점 Z에 도착할 수 없는 경우 -1을 출력한다.

예제 입력 1

13 19
1 2 100
1 3 100
1 4 1
2 5 1
3 6 1
3 4 1
4 6 1
4 7 1
5 6 10
5 8 10
6 9 10
7 10 1
8 9 10
8 11 1
9 11 1
9 12 1
10 12 2
11 13 1
12 13 3
1 13
3
8 9 10

예제 출력 1

8

1번 - 4번 - 7번 - 10번 - 12번 - 13번 순서로 방문 하는 게 최단 거리이다.

예제 입력 2

13 19
1 2 1
1 3 2
1 4 10
2 5 1
3 6 10
3 4 10
4 6 1
4 7 1
5 6 10
5 8 1
6 9 1
7 10 1
8 9 1
8 11 100
9 11 100
9 12 100
10 12 1
11 13 100
12 13 1
1 13
3
8 9 10

예제 출력 2

10

1번 - 2번 - 5번 - 8번 - 9번 - 6번 - 4번 - 7번 - 10번 - 12번 - 13번 순서로 방문 하는 게 최단 거리이다.

출처