頁面無法載入？點擊這裡可能會修復。
Placeholder

#2492

[고등부] 2025 KOI 1차대회 대비 모의고사 (2주차)

최단 경로 파괴
子任務
1秒 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
需要登入才能撰寫程式碼。