시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 97 22 14 35.000%

문제

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의 운 좋은 경로를 나타낸다.

  • 1 ≤ n ≤ 2000, 1 ≤ m ≤ 100.000
  • 1 ≤ a, b ≤ n
  • 1 ≤ w ≤ 100.000
  • 서로 다른 두 도시 사이에는 최대 하나의 도로가 존재한다.
  • 주어진 경로는 마을 a와 마을 b 사이의 최단 경로 중 하나이다.

출력

각각의 정수 t = 1 … k – 1에 대해, 각 줄마다 도로 (vt, vt+1)가 닫혔을 경우에 마을 a와 마을 b 사이의 최단 경로의 길이를 출력하라. 만약 경로가 없다면 -1을 출력하라.

예제 입력 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

힌트

sp.png

W3sicHJvYmxlbV9pZCI6IjUyNTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHViNGU0IiwiZGVzY3JpcHRpb24iOiI8cD5OaWtvbGFcdWIyOTQgQml0IFx1YjljOFx1Yzc0NFx1YzVkMCBcdWMwYjRcdWFjZTAgXHVjNzg4XHVhY2UwIEhleCBcdWI5YzhcdWM3NDRcdWM1ZDAmbmJzcDtcdWMwYWNcdWIyOTQgQW5pdGFcdWM3NTggXHViMGE4XHVjNzkwXHVjZTVjXHVhZDZjXHVjNzc0XHViMmU0LiBOaWtvbGFcdWIyOTQgXHVjOGZjXHViY2MwIFx1YzljMFx1YjNjNFx1Yjk3YyBcdWM1NDRcdWM4ZmMgXHVjNzk4IFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWM1YjRcdWMxMWMgXHViNDUwIFx1YjljOFx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM3NTggXHVjZDVjXHViMmU4IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWNjM2VcdWM1NThcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWM3NzQgXHVhY2JkXHViODVjXHViOTdjIFx1YzZiNCBcdWM4OGJcdWM3NDAgXHVhY2JkXHViODVjXHViNzdjXHVhY2UwIFx1YmQ4MFx1Yjk3NFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuIFx1YzhmY1x1YmNjMCBcdWM5YzBcdWIzYzRcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWI5YzhcdWM3NDRcdWM3NDQgXHVjNzg3XHViMjk0IFx1YzU5MVx1YmMyOVx1ZDVhNSBcdWIzYzRcdWI4NWNcdWM3NTggXHVjOWQxXHVkNTY5XHVjNzNjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViNWE0IFx1YjBhMCwgXHVjNzc0IFx1YjA5OFx1Yjc3Y1x1Yzc1OCBcdWIzMDBcdWQxYjVcdWI4MzlcdWM3NzQgXHViM2M0XHViODVjXHVjNWQwIFx1YWNmNVx1YzBhY1x1Yjk3YyBcdWQ1NThcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWIwOThcdWI3N2NcdWM3NTggXHVhZDUwXHVkMWI1XHVjNzQ0IFx1YzcyMFx1YzljMFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NThcdWM1ZWMsIFx1YzYyNFx1YzljMSBcdWQ1NThcdWI4ZThcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNzU4IFx1YjNjNFx1Yjg1Y1x1YjljYyBcdWIyZWJcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2YjQgXHVjODhiXHVjNzQwIFx1YWNiZFx1Yjg1Y1x1YzVkMCBcdWM3ODhcdWIyOTQgXHViM2M0XHViODVjXHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgTmlrb2xhXHViMjk0IFx1YWRmOCBcdWIzYzRcdWI4NWNcdWFjMDAgXHViMmViXHVkNjE0XHVjNzQ0IFx1YjU0YyBBbml0YVx1YzY0MFx1Yzc1OCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWM1NGNcdWFjZTAgXHVjMmY2XHVjNWI0IFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNzQwIDRcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNFx1YjJlNDogbiAtIFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWFjMWNcdWMyMTg7IG0gLSBcdWIzYzRcdWI4NWNcdWM3NTggXHVhYzFjXHVjMjE4OyBhIC0gQml0IFx1YjljOFx1Yzc0NChOaWtvbGFcdWFjMDAgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWI5YzhcdWM3NDQpXHVjNzU4IFx1YmM4OFx1ZDYzODsgYiAtIEhleCBcdWI5YzhcdWM3NDQoQW5pdGFcdWFjMDAgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWI5YzhcdWM3NDQpXHVjNzU4IFx1YmM4OFx1ZDYzOC48XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjNzQ0XHViNGU0XHVjNWQwXHViMjk0IDFcdWJkODBcdWQxMzAgblx1YWU0Y1x1YzljMFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViZDgwXHVjNWVjXHViNDFjXHViMmU0LiBcdWIyZTRcdWM3NGMgbVx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NDAgdSwgdiwgdyAzXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWQzZWNcdWQ1NjhcdWQ1NThcdWJhNzAgXHViM2M0XHViODVjXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWI5N2MgXHVjOTAwXHViMmU0OiBcdWI5YzhcdWM3NDQgdVx1YzY0MCBcdWI5YzhcdWM3NDQgdlx1YjI5NCBcdWFlMzhcdWM3NzQgd1x1Yzc1OCBcdWIzYzRcdWI4NWNcdWI4NWMgXHVjNzc0XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM3NDAgXHVjMjJiXHVjNzkwIGtcdWM2NDAga1x1YWMxY1x1Yzc1OCBcdWMyMmJcdWM3OTAodjxzdWI+MTxcL3N1Yj4oPWEpLCB2PHN1Yj4yPFwvc3ViPiwgJmhlbGxpcDssIHY8c3ViPms8XC9zdWI+KD1iKSlcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0IFx1YzljMFx1YWNlMCwgTmlrb2xhXHVjNzU4IFx1YzZiNCBcdWM4OGJcdWM3NDAgXHVhY2JkXHViODVjXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xICZsZTsgbiAmbGU7IDIwMDAsIDEgJmxlOyBtICZsZTsgMTAwLjAwMDxcL2xpPlxyXG5cdDxsaT4xICZsZTsgYSwgYiAmbGU7IG48XC9saT5cclxuXHQ8bGk+MSAmbGU7IHcgJmxlOyAxMDAuMDAwPFwvbGk+XHJcblx0PGxpPlx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHViNDUwIFx1YjNjNFx1YzJkYyBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHVjZDVjXHViMzAwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWIzYzRcdWI4NWNcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWM4ZmNcdWM1YjRcdWM5YzQgXHVhY2JkXHViODVjXHViMjk0IFx1YjljOFx1Yzc0NCBhXHVjNjQwIFx1YjljOFx1Yzc0NCBiIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjIFx1YzkxMSBcdWQ1NThcdWIwOThcdWM3NzRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVjODE1XHVjMjE4IHQgPSAxICZoZWxsaXA7IGsgJm5kYXNoOyAxXHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHVhYzAxIFx1YzkwNFx1YjljOFx1YjJlNCBcdWIzYzRcdWI4NWMgKHY8c3ViPnQ8XC9zdWI+LCB2PHN1Yj50KzE8XC9zdWI+KVx1YWMwMCBcdWIyZWJcdWQ2MTRcdWM3NDQgXHVhY2JkXHVjNmIwXHVjNWQwIFx1YjljOFx1Yzc0NCBhXHVjNjQwIFx1YjljOFx1Yzc0NCBiIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuIFx1YjljY1x1YzU3ZCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjNWM2XHViMmU0XHViYTc0IC0xXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJzcC5wbmdcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC8xZGRkZjUxYS00NjBlLTQ5NTUtOTllYy0yMjU5ODk3NTQ0MWVcLy1cL3ByZXZpZXdcL1wiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTI1MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNob3J0ZXN0IHBhdGhzIiwiZGVzY3JpcHRpb24iOiI8cD5OaWtvbGEgbGl2ZXMgaW4gQml0dG93biBhbmQgaGUgaXMgaW4gbG92ZSB3aXRoIGhpcyBnaXJsZnJpZW5kIEFuaXRhIGZyb20gYSB0b3duIGNhbGxlZCBIZXh0b3duLiBOaWtvbGEga25vd3MgdGhlIGNvdW50cnkgbWFwIHZlcnkgd2VsbCwgYW5kIGhlIGZvdW5kIHRoZSBzaG9ydGVzdCBwYXRoIGJldHdlZW4gdGhlc2UgdHdvIHRvd25zLiBIZSBjYWxscyB0aGlzIHBhdGggbHVja3kgcGF0aC4gVGhlIG1hcCBvZiB0aGUgY291bnRyeSBjYW4gYmUgZGVzY3JpYmVkIGFzIGEgY29sbGVjdGlvbiBvZiB0b3ducyBjb25uZWN0ZWQgd2l0aCBiaWRpcmVjdGlvbmFsIHJvYWRzLjxcL3A+XHJcblxyXG48cD5PbmUgZGF5IHRoZSBwcmVzaWRlbnQgb2YgdGhpcyBjb3VudHJ5IGRlY2lkZWQgdGhhdCB0aGVyZSBhcmUgZ29pbmcgdG8gYmUgc29tZSB3b3JrcyBvbiB0aGUgcm9hZHMuIEluIG9yZGVyIHRvIHVwaG9sZCB0aGUgdHJhZmZpYyBpbiB0aGUgY291bnRyeSwgb25seSBvbmUgcm9hZCBpcyBnb2luZyB0byBiZSBjbG9zZWQgcGVyIGRheS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIGVhY2ggcm9hZCBvbiB0aGUgbHVja3kgcGF0aCwgTmlrb2xhIHdhbnRzIHRvIGtub3cgdGhlIGxlbmd0aCBvZiB0aGUgc2hvcnRlc3QgcGF0aCBiZXR3ZWVuIEFuaXRhIGFuZCBoaW0gaWYgdGhhdCByb2FkIGlzIGNsb3NlZC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGZvdXIgaW50ZWdlcnM6IG4gJm1kYXNoOyB0aGUgbnVtYmVyIG9mIGNpdGllczsgbSAmbWRhc2g7IHRoZSBudW1iZXIgb2Ygcm9hZHMgYmV0d2VlbiB0aGVzZSB0b3duczsgYSAmbWRhc2g7IGluZGV4IG9mIHRvd24gQml0dG93biB3aGVyZSBOaWtvbGEgbGl2ZXM7IGIgJm1kYXNoOyB0aGUgaW5kZXggb2YgdG93biBIZXh0b3duIHdoZXJlIEFuaXRhIGxpdmVzLiBUb3ducyBhcmUgaW5kZXhlZCB3aXRoIG51bWJlcnMgMSwgMiwmaGVsbGlwOywgbi4gTmV4dCBtIGxpbmVzIHNwZWNpZnkgcm9hZHM6IGVhY2ggbGluZSBjb250YWlucyB0aHJlZSBpbnRlZ2VyczogdSwgdiBhbmQgdyAmbmRhc2g7IHRoZXJlIGV4aXN0IHJvYWQgYmV0d2VlbiB0b3ducyB1IGFuZCB2IHdpdGggbGVuZ3RoIHcuIExhc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgbnVtYmVyIGsgZm9sbG93ZWQgYnkgayBudW1iZXJzIGEgPSB2PHN1Yj4xPFwvc3ViPiwgdjxzdWI+MjxcL3N1Yj4sICZoZWxsaXA7LCB2PHN1Yj5rPFwvc3ViPiA9IGIgJm5kYXNoOyB0aGUgbHVja3kgcGF0aCB0aGF0IE5pa29sYSB1c2VzLiZuYnNwOzxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgJmxlOyBuICZsZTsgMjAwMCwgMSAmbGU7IG0gJmxlOyAxMDAuMDAwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyBhLCBiICZsZTsgbjxcL2xpPlxyXG5cdDxsaT4xICZsZTsgdyAmbGU7IDEwMC4wMDA8XC9saT5cclxuXHQ8bGk+VGhlcmUgaXMgYXQgbW9zdCBvbmUgcm9hZCBiZXR3ZWVuIGVhY2ggcGFpciBvZiBjaXRpZXMuPFwvbGk+XHJcblx0PGxpPllvdSBtYXkgYXNzdW1lIHRoYXQgdGhlIGdpdmVuIHBhdGggaXMgb25lIG9mIHRoZSBzaG9ydGVzdCBwYXRocyB0aGF0IGNvbm5lY3RzIGdpdmVuIHR3byBjaXRpZXMgYSBhbmQgYi4mbmJzcDs8XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBldmVyeSBpbnRlZ2VyIHQgPSAxICZoZWxsaXA7IGsgJm5kYXNoOyAxLCBpbiBzZXBhcmF0ZSBsaW5lLCBwcmludCB0aGUgbGVuZ3RoIG9mIHRoZSBzaG9ydGVzdCBwYXRoIGJldHdlZW4gY2l0aWVzIGEgYW5kIGIsIGlmIHRoZSByb2FkICh2PHN1Yj50PFwvc3ViPiwgdjxzdWI+dCsxPFwvc3ViPikgaXMgY2xvc2VkLiBJZiB0aGVyZSBpcyBubyBzdWNoIHBhdGgsIG91dHB1dCAmbGRxdW87LTEmcmRxdW87IHdpdGhvdXQgcXVvdGVzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC9zcC5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzJweDsgd2lkdGg6MzUwcHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Balkan Olympiad in Informatics > BOI 2012 2번