문제
석환나라에는 N개의 도시가 있고, M개의 양방향 도로가 이 도시들을 연결합니다. 각 도로를 지날 때에는 일정한 시간이 걸립니다. 어떠한 두 도시를 선택하더라도 그 두 도시를 직접 연결하는 도로는 최대 한 개입니다. 석환나라에는 한 개의 고속도로가 있는데 이 고속도로는 두 종점 A와 B가 있고, A에서 B로 갈 때는 고속도로로 가는 것이 가장 빠릅니다.
그런데 고속도로는 각종 테러조직의 타겟이 되기 때문에 고속도로를 구성하고 있는 한 도로가 아예 폭파될 수 있습니다. 석환나라의 왕인 석환이는 이런 경우를 고려하여 각 도로가 폭파되는 경우에 A에서 B로 갈 때 걸리는 최소 시간을 알아보고 싶어합니다. 각 도로가 폭파되는 경우 A에서 B로 가는 최소 시간을 구하는 프로그램을 작성하세요
입력
첫 번째 줄에는 도시의 수 N (1 ≤ N ≤ 2,000)과 도로의 수 M (1 ≤ M ≤ 100,000)과 고속도로의 두 종점의 번호 A, B (1 ≤ A, B ≤ N)가 주어집니다.
두 번째 줄부터 M개의 줄에는 각 도로의 정보가 주어집니다. 앞 두 수는 도로의 양 끝 도시의 번호이고 세 번째 수는 도로를 지날 때 걸리는 시간(≤ 100,000)입니다.
마지막 줄에는 고속도로를 지나는 도시의 수 K와 고속도로를 지나는 도시의 번호가 주어집니다. 고속도로를 지나는 도시의 번호는 A에서 시작해서 B로 끝나고, 고속도로는 A에서 B로 가는 최단경로 중 하나임이 보장됩니다.
출력
첫 번째 줄부터 K-1번째 줄까지, 고속도로의 각 도로가 폭파될 때 A에서 B로 갈 때 걸리는 최소 시간을 출력합니다. 만약 A에서 B로 가지 못한다면 -1을 출력합니다.
< 입출력 제약 >
40%의 데이터는 1 ≤ N ≤ 300, 1 ≤ M ≤ 3,000이다.
60%의 데이터는 1 ≤ N ≤ 2,000, 1 ≤ M ≤ 100,000이다.
예제
5 6 1 5
1 2 1
2 3 3
2 5 100
3 4 3
3 5 5
4 5 3
4 1 2 3 5
-1
101
10
출처
Balkan Olympiad in Informatics 2012 번역 functionx
로그인해야 코드를 작성할 수 있어요.