시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB121224915921.060%

문제

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을 출력하라.

제한

  • 1 ≤ n ≤ 2000, 1 ≤ m ≤ 100.000
  • 1 ≤ a, b ≤ n
  • 1 ≤ w ≤ 100.000
  • 서로 다른 두 도시 사이에는 최대 하나의 도로가 존재한다.
  • 주어진 경로는 마을 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

-1
101
10

힌트

W3sicHJvYmxlbV9pZCI6IjUyNTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHViNGU0IiwiZGVzY3JpcHRpb24iOiI8cD5OaWtvbGFcdWIyOTQgQml0IFx1YjljOFx1Yzc0NFx1YzVkMCBcdWMwYjRcdWFjZTAgXHVjNzg4XHVhY2UwIEhleCBcdWI5YzhcdWM3NDRcdWM1ZDAmbmJzcDtcdWMwYWNcdWIyOTQgQW5pdGFcdWM3NTggXHViMGE4XHVjNzkwXHVjZTVjXHVhZDZjXHVjNzc0XHViMmU0LiBOaWtvbGFcdWIyOTQgXHVjOGZjXHViY2MwIFx1YzljMFx1YjNjNFx1Yjk3YyBcdWM1NDRcdWM4ZmMgXHVjNzk4IFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWM1YjRcdWMxMWMgXHViNDUwIFx1YjljOFx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM3NTggXHVjZDVjXHViMmU4IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWNjM2VcdWM1NThcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWM3NzQgXHVhY2JkXHViODVjXHViOTdjIFx1YzZiNCBcdWM4OGJcdWM3NDAgXHVhY2JkXHViODVjXHViNzdjXHVhY2UwIFx1YmQ4MFx1Yjk3NFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1YzhmY1x1YmNjMCBcdWM5YzBcdWIzYzRcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWI5YzhcdWM3NDRcdWM3NDQgXHVjNzg3XHViMjk0IFx1YzU5MVx1YmMyOVx1ZDVhNSBcdWIzYzRcdWI4NWNcdWM3NTggXHVjOWQxXHVkNTY5XHVjNzNjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IFx1YjBhMCwgXHVjNzc0IFx1YjA5OFx1Yjc3Y1x1Yzc1OCBcdWIzMDBcdWQxYjVcdWI4MzlcdWM3NzQgXHViM2M0XHViODVjXHVjNWQwIFx1YWNmNVx1YzBhY1x1Yjk3YyBcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWIwOThcdWI3N2NcdWM3NTggXHVhZDUwXHVkMWI1XHVjNzQ0IFx1YzcyMFx1YzljMFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NThcdWM1ZWMsIFx1YzYyNFx1YzljMSBcdWQ1NThcdWI4ZThcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNzU4IFx1YjNjNFx1Yjg1Y1x1YjljYyBcdWIyZWJcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2YjQgXHVjODhiXHVjNzQwIFx1YWNiZFx1Yjg1Y1x1YzVkMCBcdWM3ODhcdWIyOTQgXHViM2M0XHViODVjXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgTmlrb2xhXHViMjk0IFx1YWRmOCBcdWIzYzRcdWI4NWNcdWFjMDAgXHViMmViXHVkNjE0XHVjNzQ0IFx1YjU0YyBBbml0YVx1YzY0MFx1Yzc1OCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWM1NGNcdWFjZTAgXHVjMmY2XHVjNWI0IFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNzQwIDRcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNFx1YjJlNDogbiAtIFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWFjMWNcdWMyMTg7IG0gLSBcdWIzYzRcdWI4NWNcdWM3NTggXHVhYzFjXHVjMjE4OyBhIC0gQml0IFx1YjljOFx1Yzc0NChOaWtvbGFcdWFjMDAgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWI5YzhcdWM3NDQpXHVjNzU4IFx1YmM4OFx1ZDYzODsgYiAtIEhleCBcdWI5YzhcdWM3NDQoQW5pdGFcdWFjMDAgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWI5YzhcdWM3NDQpXHVjNzU4IFx1YmM4OFx1ZDYzOC48XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjNzQ0XHViNGU0XHVjNWQwXHViMjk0IDFcdWJkODBcdWQxMzAgblx1YWU0Y1x1YzljMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDgwXHVjNWVjXHViNDFjXHViMmU0LiBcdWIyZTRcdWM3NGMgbVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NDAgdSwgdiwgdyAzXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWJhNzAgXHViM2M0XHViODVjXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWI5N2MgXHVjOTAwXHViMmU0OiBcdWI5YzhcdWM3NDQgdVx1YzY0MCBcdWI5YzhcdWM3NDQgdlx1YjI5NCBcdWFlMzhcdWM3NzQgd1x1Yzc1OCBcdWIzYzRcdWI4NWNcdWI4NWMgXHVjNzc0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM3NDAgXHVjMjJiXHVjNzkwIGtcdWM2NDAga1x1YWMxY1x1Yzc1OCBcdWMyMmJcdWM3OTAodjxzdWI+MTxcL3N1Yj4oPWEpLCB2PHN1Yj4yPFwvc3ViPiwgJmhlbGxpcDssIHY8c3ViPms8XC9zdWI+KD1iKSlcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0IFx1YzljMFx1YWNlMCwgTmlrb2xhXHVjNzU4IFx1YzZiNCBcdWM4OGJcdWM3NDAgXHVhY2JkXHViODVjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVjODE1XHVjMjE4IHQgPSAxICZoZWxsaXA7IGsgJm5kYXNoOyAxXHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHVhYzAxIFx1YzkwNFx1YjljOFx1YjJlNCBcdWIzYzRcdWI4NWMgKHY8c3ViPnQ8XC9zdWI+LCB2PHN1Yj50KzE8XC9zdWI+KVx1YWMwMCBcdWIyZWJcdWQ2MTRcdWM3NDQgXHVhY2JkXHVjNmIwXHVjNWQwIFx1YjljOFx1Yzc0NCBhXHVjNjQwIFx1YjljOFx1Yzc0NCBiIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuIFx1YjljY1x1YzU3ZCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjNWM2XHViMmU0XHViYTc0IC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC84YjllNDUwOC0zZjcxLTRmMTctOGM1NS0xMGI4M2U5OWMzMjBcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDMzM3B4OyBoZWlnaHQ6IDEyN3B4O1wiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBuICZsZTsgMjAwMCwgMSAmbGU7IG0gJmxlOyAxMDAuMDAwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBhLCBiICZsZTsgbjxcL2xpPlxyXG5cdDxsaT4xICZsZTsgdyAmbGU7IDEwMC4wMDA8XC9saT5cclxuXHQ8bGk+XHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWI0NTAgXHViM2M0XHVjMmRjIFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVkNTU4XHViMDk4XHVjNzU4IFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzhmY1x1YzViNFx1YzljNCBcdWFjYmRcdWI4NWNcdWIyOTQgXHViOWM4XHVjNzQ0IGFcdWM2NDAgXHViOWM4XHVjNzQ0IGIgXHVjMGFjXHVjNzc0XHVjNzU4IFx1Y2Q1Y1x1YjJlOCBcdWFjYmRcdWI4NWMgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjUyNTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTaG9ydGVzdCBwYXRocyIsImRlc2NyaXB0aW9uIjoiPHA+Tmlrb2xhIGxpdmVzIGluIEJpdHRvd24gYW5kIGhlIGlzIGluIGxvdmUgd2l0aCBoaXMgZ2lybGZyaWVuZCBBbml0YSBmcm9tIGEgdG93biBjYWxsZWQgSGV4dG93bi4gTmlrb2xhIGtub3dzIHRoZSBjb3VudHJ5IG1hcCB2ZXJ5IHdlbGwsIGFuZCBoZSBmb3VuZCB0aGUgc2hvcnRlc3QgcGF0aCBiZXR3ZWVuIHRoZXNlIHR3byB0b3ducy4gSGUgY2FsbHMgdGhpcyBwYXRoIGx1Y2t5IHBhdGguIFRoZSBtYXAgb2YgdGhlIGNvdW50cnkgY2FuIGJlIGRlc2NyaWJlZCBhcyBhIGNvbGxlY3Rpb24gb2YgdG93bnMgY29ubmVjdGVkIHdpdGggYmlkaXJlY3Rpb25hbCByb2Fkcy48XC9wPlxyXG5cclxuPHA+T25lIGRheSB0aGUgcHJlc2lkZW50IG9mIHRoaXMgY291bnRyeSBkZWNpZGVkIHRoYXQgdGhlcmUgYXJlIGdvaW5nIHRvIGJlIHNvbWUgd29ya3Mgb24gdGhlIHJvYWRzLiBJbiBvcmRlciB0byB1cGhvbGQgdGhlIHRyYWZmaWMgaW4gdGhlIGNvdW50cnksIG9ubHkgb25lIHJvYWQgaXMgZ29pbmcgdG8gYmUgY2xvc2VkIHBlciBkYXkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkZvciBlYWNoIHJvYWQgb24gdGhlIGx1Y2t5IHBhdGgsIE5pa29sYSB3YW50cyB0byBrbm93IHRoZSBsZW5ndGggb2YgdGhlIHNob3J0ZXN0IHBhdGggYmV0d2VlbiBBbml0YSBhbmQgaGltIGlmIHRoYXQgcm9hZCBpcyBjbG9zZWQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBmb3VyIGludGVnZXJzOiBuICZtZGFzaDsgdGhlIG51bWJlciBvZiBjaXRpZXM7IG0gJm1kYXNoOyB0aGUgbnVtYmVyIG9mIHJvYWRzIGJldHdlZW4gdGhlc2UgdG93bnM7IGEgJm1kYXNoOyBpbmRleCBvZiB0b3duIEJpdHRvd24gd2hlcmUgTmlrb2xhIGxpdmVzOyBiICZtZGFzaDsgdGhlIGluZGV4IG9mIHRvd24gSGV4dG93biB3aGVyZSBBbml0YSBsaXZlcy4gVG93bnMgYXJlIGluZGV4ZWQgd2l0aCBudW1iZXJzIDEsIDIsJmhlbGxpcDssIG4uIE5leHQgbSBsaW5lcyBzcGVjaWZ5IHJvYWRzOiBlYWNoIGxpbmUgY29udGFpbnMgdGhyZWUgaW50ZWdlcnM6IHUsIHYgYW5kIHcgJm5kYXNoOyB0aGVyZSBleGlzdCByb2FkIGJldHdlZW4gdG93bnMgdSBhbmQgdiB3aXRoIGxlbmd0aCB3LiBMYXN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIG51bWJlciBrIGZvbGxvd2VkIGJ5IGsgbnVtYmVycyBhID0gdjxzdWI+MTxcL3N1Yj4sIHY8c3ViPjI8XC9zdWI+LCAmaGVsbGlwOywgdjxzdWI+azxcL3N1Yj4gPSBiICZuZGFzaDsgdGhlIGx1Y2t5IHBhdGggdGhhdCBOaWtvbGEgdXNlcy4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZXZlcnkgaW50ZWdlciB0ID0gMSAmaGVsbGlwOyBrICZuZGFzaDsgMSwgaW4gc2VwYXJhdGUgbGluZSwgcHJpbnQgdGhlIGxlbmd0aCBvZiB0aGUgc2hvcnRlc3QgcGF0aCBiZXR3ZWVuIGNpdGllcyBhIGFuZCBiLCBpZiB0aGUgcm9hZCAodjxzdWI+dDxcL3N1Yj4sIHY8c3ViPnQrMTxcL3N1Yj4pIGlzIGNsb3NlZC4gSWYgdGhlcmUgaXMgbm8gc3VjaCBwYXRoLCBvdXRwdXQgJmxkcXVvOy0xJnJkcXVvOyB3aXRob3V0IHF1b3Rlcy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC84YjllNDUwOC0zZjcxLTRmMTctOGM1NS0xMGI4M2U5OWMzMjBcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDMzM3B4OyBoZWlnaHQ6IDEyN3B4O1wiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5GaWd1cmUgMS4gRGVzY3JpcHRpb24gb2YgdGhlIGV4YW1wbGU8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IG4gJmxlOyAyMDAwLCAxICZsZTsgbSAmbGU7IDEwMC4wMDA8XC9saT5cclxuXHQ8bGk+MSAmbGU7IGEsIGIgJmxlOyBuPFwvbGk+XHJcblx0PGxpPjEgJmxlOyB3ICZsZTsgMTAwLjAwMDxcL2xpPlxyXG5cdDxsaT5UaGVyZSBpcyBhdCBtb3N0IG9uZSByb2FkIGJldHdlZW4gZWFjaCBwYWlyIG9mIGNpdGllcy48XC9saT5cclxuXHQ8bGk+WW91IG1heSBhc3N1bWUgdGhhdCB0aGUgZ2l2ZW4gcGF0aCBpcyBvbmUgb2YgdGhlIHNob3J0ZXN0IHBhdGhzIHRoYXQgY29ubmVjdHMgZ2l2ZW4gdHdvIGNpdGllcyBhIGFuZCBiLiZuYnNwOzxcL2xpPlxyXG48XC91bD5cclxuIn1d

출처

Olympiad > Balkan Olympiad in Informatics > BOI 2012 2번