시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 1228 | 254 | 163 | 21.224% |
Nikola는 Bit 마을에 살고 있고 Hex 마을에 사는 Anita의 남자친구이다. Nikola는 주변 지도를 아주 잘 알고 있어서 두 마을 사이의 최단 경로를 찾았다. 그리고 이 경로를 운 좋은 경로라고 부르기로 했다. 주변 지도는 서로 다른 마을을 잇는 양방향 도로의 집합으로 표현된다.
어떤 날, 이 나라의 대통령이 도로에 공사를 하기로 했다. 나라의 교통을 유지하기 위하여, 오직 하루에 하나의 도로만 닫기로 했다.
운 좋은 경로에 있는 도로에 대해서, Nikola는 그 도로가 닫혔을 때 Anita와의 최단 경로의 길이를 알고 싶어 한다.
입력의 첫째 줄은 4개의 정수로 이루어진다: n - 도시의 개수; m - 도로의 개수; a - Bit 마을(Nikola가 살고 있는 마을)의 번호; b - Hex 마을(Anita가 살고 있는 마을)의 번호.
마을들에는 1부터 n까지의 번호가 부여된다. 다음 m개의 줄은 u, v, w 3개의 정수를 포함하며 도로에 대한 정보를 준다: 마을 u와 마을 v는 길이 w의 도로로 이어져 있다.
입력의 마지막 줄은 숫자 k와 k개의 숫자(v1(=a), v2, …, vk(=b))로 이루어 지고, Nikola의 운 좋은 경로를 나타낸다.
각각의 정수 t = 1 … k – 1에 대해, 각 줄마다 도로 (vt, vt+1)가 닫혔을 경우에 마을 a와 마을 b 사이의 최단 경로의 길이를 출력하라. 만약 경로가 없다면 -1을 출력하라.
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
Olympiad > Balkan Olympiad in Informatics > BOI 2012 2번