페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8304
서브태스크

최단 경로 파괴 1s 128MB

문제

1번 부터 N번까지 차례로 번호가 매겨진 N개의 마을은 M개의 양방향 도로로 연결되어 있다.

정올이는 A번 마을에서 B번 마을로 이동할 수 있는 최단 경로를 알게 되어 해당 경로를 운 좋은 경로라고 이름 붙였다.

그런 정올이가 부러웠던 한글이는 운 좋은 경로에 있는 도로 중 하나를 파괴하여 아무도 못지나가게 하는 계획을 세웠다.

정올이를 위해 한글이가 운 좋은 경로에 있는 도로 중 하나의 도로를 파괴했을 때를, A번 마을에서 B번 마을로 갈 수 있는 최단 거리를 구하는 프로그램을 작성해주자.


입력

첫 줄에 네 정수 N, M, A, B가 주어진다.

이어 M줄에 걸쳐 세 정수 u, v, w가 주어진다. 이는 u번 마을과 v번 마을이 w 길이의 도로로 연결되어 있다는 의미다.

마지막 줄에 정수 K와 이어 K개의 정수 V_1, V_2, \cdots, V_K가 주어진다. 이는 길이 K의 "운 좋은 경로"를 의미한다.

  • 1 \le N \le 2,000

  • 1 \le M \le 100,000

  • 1 \le A, B, u, v \le N

  • 1 \le w \le 100,000

  • V_1 = A, V_K = B

  • 서로 다른 두 도시 사이에는 최대 하나의 도로가 존재한다.

  • 최단 경로는 주어진 경로는 마을 A와 마을 B 사이의 최단 경로 중 하나이다.


출력

각각의 정수 i (1 \le i < K)에 대해, 각 줄마다 도로 (V_i, V_{i+1})가 파괴되었을 경우에 마을 A와 마을 B 사이의 최단 경로의 길이를 출력하라. 만약 경로가 없다면 -1을 출력하라.


부분문제

번호 점수 조건
#120점

N \le 20

#230점

도로가 3개 이상 연결된 마을은 V_i에만 존재한다. (1 \le i \le K)

#350점

추가 제약 조건 없음


예제 #1

7 11 1 4
1 2 1
1 5 1
1 6 4
2 3 3
2 5 5
2 6 1
6 3 5
5 3 7
3 4 3
5 7 1
6 4 6
4 1 2 3 4
10
8
8

예제 #2

4 4 2 4
3 2 1
2 1 4
3 1 3
4 1 2
4 2 3 1 4
6
6
-1


출처

BOI(Balkan) 2012
로그인해야 코드를 작성할 수 있어요.