시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 479 109 73 18.961%

문제

2015년 구단에서 방출된 셰브첸코는 한때 그의 팬이었던 구단주 로만 아브라히모비치의 도움으로 러시아의 경찰이 되었다.

어느날 그는 그가 감시를 하고 있는 마피아 조직에서 대규모 이동이 있음을 감지했다. 마피아는 고속도로를 통해서 이동을 하는데 고속도로망은 n개의 톨게이트와 그 사이를 있는 m개의 고속도로로 이루어져있다. 고속도로의 중간에서 밖으로 나가거나 중간으로 들어오지는 못한다고 하자. 즉 모든 이동은 톨게이트와 고속도로를 거쳐서 이루어져야 된다는 것이다. 마피아의 시작점과 도착점이 주어질 때 우리는 몇 개의 톨게이트를 점거해서 마피아가 시작점에서 도착점까지 우리의 점거된 톨게이트를 지나지 않고서는 도착할 수 없게 하고 싶다. 그런데 톨게이트를 점거하는데에는 각각의 톨게이트마다 고유한 비용이 든다.

이때 점거비를 최소화 하며 마피아의 움직임을 막기 위해 점거해야되는 도시들을 출력하여라.

입력

첫 줄에는 톨게이트의 개수 n과 고속도로의 개수 m이 주어진다.(1<=n<=200, 1<=m<=20000) 톨게이트의 번호는 1부터 n까지로 주어진다고 할 때, 다음 줄에는 마피아의 시작점과 도착점이 주어진다. 그리고 그 다음 n개의 줄에는 각 톨게이트별 점거비용이 나온다. 그 뒤 m개의 줄에는 톨게이트를 잇는 고속도로들이 주어진다.

출력

점거비를 최소화 하며 마피아의 움직임을 막기 위해 점거해야되는 도시들을 오름차순으로 출력하여라.

예제 입력 1

5 6
5 3
2
4
8
3
10
1 5
1 2
2 4
4 5
2 3
3 4

예제 출력 1

1 4
W3sicHJvYmxlbV9pZCI6IjEyMTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5YzhcdWQ1M2NcdWM1NDQiLCJkZXNjcmlwdGlvbiI6IjxwPjIwMTVcdWIxNDQgXHVhZDZjXHViMmU4XHVjNWQwXHVjMTFjIFx1YmMyOVx1Y2Q5Y1x1YjQxYyBcdWMxNzBcdWJlMGNcdWNjYjhcdWNmNTRcdWIyOTQgXHVkNTVjXHViNTRjIFx1YWRmOFx1Yzc1OCBcdWQzMmNcdWM3NzRcdWM1YzhcdWIzNTggXHVhZDZjXHViMmU4XHVjOGZjIFx1Yjg1Y1x1YjljYyBcdWM1NDRcdWJlMGNcdWI3N2NcdWQ3ODhcdWJhYThcdWJlNDRcdWNlNThcdWM3NTggXHViM2M0XHVjNmMwXHVjNzNjXHViODVjIFx1YjdlY1x1YzJkY1x1YzU0NFx1Yzc1OCBcdWFjYmRcdWNjMzBcdWM3NzQgXHViNDE4XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWIyOTBcdWIwYTAgXHVhZGY4XHViMjk0IFx1YWRmOFx1YWMwMCBcdWFjMTBcdWMyZGNcdWI5N2MgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWI5YzhcdWQ1M2NcdWM1NDQgXHVjODcwXHVjOWMxXHVjNWQwXHVjMTFjIFx1YjMwMFx1YWRkY1x1YmFhOCBcdWM3NzRcdWIzZDlcdWM3NzQgXHVjNzg4XHVjNzRjXHVjNzQ0IFx1YWMxMFx1YzljMFx1ZDU4OFx1YjJlNC4gXHViOWM4XHVkNTNjXHVjNTQ0XHViMjk0IFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWQxYjVcdWQ1NzRcdWMxMWMgXHVjNzc0XHViM2Q5XHVjNzQ0IFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWI5ZGRcdWM3NDAgblx1YWMxY1x1Yzc1OCBcdWQxYThcdWFjOGNcdWM3NzRcdWQyYjhcdWM2NDAgXHVhZGY4IFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWM3ODhcdWIyOTQgbVx1YWMxY1x1Yzc1OCBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4XHVjNzg4XHViMmU0LiBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWM3NTggXHVjOTExXHVhYzA0XHVjNWQwXHVjMTFjIFx1YmMxNlx1YzczY1x1Yjg1YyBcdWIwOThcdWFjMDBcdWFjNzBcdWIwOTggXHVjOTExXHVhYzA0XHVjNzNjXHViODVjIFx1YjRlNFx1YzViNFx1YzYyNFx1YzljMFx1YjI5NCBcdWJhYmJcdWQ1NWNcdWIyZTRcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWM5ODkgXHViYWE4XHViNGUwIFx1Yzc3NFx1YjNkOVx1Yzc0MCBcdWQxYThcdWFjOGNcdWM3NzRcdWQyYjhcdWM2NDAgXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHViOTdjIFx1YWM3MFx1Y2NkMFx1YzExYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzhcdWM1N2MgXHViNDFjXHViMmU0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViOWM4XHVkNTNjXHVjNTQ0XHVjNzU4IFx1YzJkY1x1Yzc5MVx1YzgxMFx1YWNmYyBcdWIzYzRcdWNjMjlcdWM4MTBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YyBcdWM2YjBcdWI5YWNcdWIyOTQgXHViYTg3IFx1YWMxY1x1Yzc1OCBcdWQxYThcdWFjOGNcdWM3NzRcdWQyYjhcdWI5N2MgXHVjODEwXHVhYzcwXHVkNTc0XHVjMTFjIFx1YjljOFx1ZDUzY1x1YzU0NFx1YWMwMCBcdWMyZGNcdWM3OTFcdWM4MTBcdWM1ZDBcdWMxMWMgXHViM2M0XHVjYzI5XHVjODEwXHVhZTRjXHVjOWMwIFx1YzZiMFx1YjlhY1x1Yzc1OCBcdWM4MTBcdWFjNzBcdWI0MWMgXHVkMWE4XHVhYzhjXHVjNzc0XHVkMmI4XHViOTdjIFx1YzljMFx1YjA5OFx1YzljMCBcdWM1NGFcdWFjZTBcdWMxMWNcdWIyOTQgXHViM2M0XHVjYzI5XHVkNTYwIFx1YzIxOCBcdWM1YzZcdWFjOGMgXHVkNTU4XHVhY2UwIFx1YzJmNlx1YjJlNC4gXHVhZGY4XHViN2YwXHViMzcwIFx1ZDFhOFx1YWM4Y1x1Yzc3NFx1ZDJiOFx1Yjk3YyBcdWM4MTBcdWFjNzBcdWQ1NThcdWIyOTRcdWIzNzBcdWM1ZDBcdWIyOTQgXHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDFhOFx1YWM4Y1x1Yzc3NFx1ZDJiOFx1YjljOFx1YjJlNCBcdWFjZTBcdWM3MjBcdWQ1NWMgXHViZTQ0XHVjNmE5XHVjNzc0IFx1YjRlMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViNTRjIFx1YzgxMFx1YWM3MFx1YmU0NFx1Yjk3YyBcdWNkNWNcdWMxOGNcdWQ2NTQgXHVkNTU4XHViYTcwIFx1YjljOFx1ZDUzY1x1YzU0NFx1Yzc1OCBcdWM2YzBcdWM5YzFcdWM3ODRcdWM3NDQgXHViOWM5XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM4MTBcdWFjNzBcdWQ1NzRcdWM1N2NcdWI0MThcdWIyOTQgXHViM2M0XHVjMmRjXHViNGU0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMWE4XHVhYzhjXHVjNzc0XHVkMmI4XHVjNzU4IFx1YWMxY1x1YzIxOCBuXHVhY2ZjIFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWFjMWNcdWMyMTggbVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuKDEmbHQ7PW4mbHQ7PTIwMCwgMSZsdDs9bSZsdDs9MjAwMDApIFx1ZDFhOFx1YWM4Y1x1Yzc3NFx1ZDJiOFx1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgMVx1YmQ4MFx1ZDEzMCBuXHVhZTRjXHVjOWMwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNFx1YWNlMCBcdWQ1NjAgXHViNTRjLCBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjljOFx1ZDUzY1x1YzU0NFx1Yzc1OCBcdWMyZGNcdWM3OTFcdWM4MTBcdWFjZmMgXHViM2M0XHVjYzI5XHVjODEwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhZGY4XHViOWFjXHVhY2UwIFx1YWRmOCBcdWIyZTRcdWM3NGMgblx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1ZDFhOFx1YWM4Y1x1Yzc3NFx1ZDJiOFx1YmNjNCBcdWM4MTBcdWFjNzBcdWJlNDRcdWM2YTlcdWM3NzQgXHViMDk4XHVjNjI4XHViMmU0LiBcdWFkZjggXHViNGE0IG1cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDFhOFx1YWM4Y1x1Yzc3NFx1ZDJiOFx1Yjk3YyBcdWM3ODdcdWIyOTQgXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHViNGU0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM4MTBcdWFjNzBcdWJlNDRcdWI5N2MgXHVjZDVjXHVjMThjXHVkNjU0IFx1ZDU1OFx1YmE3MCBcdWI5YzhcdWQ1M2NcdWM1NDRcdWM3NTggXHVjNmMwXHVjOWMxXHVjNzg0XHVjNzQ0IFx1YjljOVx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjODEwXHVhYzcwXHVkNTc0XHVjNTdjXHViNDE4XHViMjk0IFx1YjNjNFx1YzJkY1x1YjRlNFx1Yzc0NCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjZDljXHViODI1XHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEyMTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNYWZpYSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIHBvbGljZSBpbiBCeXRlbGFuZCBnb3QgYW4gYW5vbnltb3VzIHRpcCB0aGF0IHRoZSBsb2NhbCBtYVx1ZmIwMWEgYm9zc2VzIGFyZSBwbGFubmluZyBhIGJpZyB0cmFuc3BvcnQgZnJvbSB0aGUgaGFyYm91ciB0byBvbmUgb2YgdGhlIHNlY3JldCB3YXJlaG91c2VzIGluIHRoZSBjb3VudHJ5c2lkZS4gVGhlIHBvbGljZSBrbm93cyB0aGUgZGF0ZSBvZiB0aGUgdHJhbnNwb3J0IGFuZCB0aGV5IGtub3cgdGhhdCB0aGUgdHJhbnNwb3J0IHdpbGwgdXNlIHRoZSBuYXRpb25hbCBoaWdod2F5IG5ldHdvcmsuPFwvcD5cclxuXHJcbjxwPlRoZSBoaWdod2F5IG5ldHdvcmsgY29uc2lzdHMgb2YgdHdvLXdheSBoaWdod2F5IHNlZ21lbnRzLCBlYWNoIHNlZ21lbnQgZGlyZWN0bHkgY29ubmVjdGluZyB0d28gZGlzdGluY3QgdG9sbCBzdGF0aW9ucy4gQSB0b2xsIHN0YXRpb24gbWF5IGJlIGNvbm5lY3RlZCB3aXRoIG1hbnkgb3RoZXIgc3RhdGlvbnMuIEEgdmVoaWNsZSBjYW4gZW50ZXIgb3IgZXhpdCB0aGUgaGlnaHdheSBuZXR3b3JrIGF0IHRvbGwgc3RhdGlvbnMgb25seS4gVGhlIG1hXHVmYjAxYSB0cmFuc3BvcnQgaXMga25vd24gdG8gZW50ZXIgdGhlIGhpZ2h3YXlzIGF0IHRoZSB0b2xsIHN0YXRpb24gY2xvc2VzdCB0byB0aGUgaGFyYm91ciBhbmQgbGVhdmUgaXQgYXQgdGhlIHRvbGwgc3RhdGlvbiBjbG9zZXN0IHRvIHRoZSB3YXJlaG91c2UgKGl0IHdpbGwgbm90IGxlYXZlIGFuZCByZS1lbnRlciB0aGUgaGlnaHdheXMgaW4gYmV0d2VlbikuIFNwZWNpYWwgcG9saWNlIHNxdWFkcyBhcmUgdG8gYmUgbG9jYXRlZCBpbiBzZWxlY3RlZCB0b2xsIHN0YXRpb25zLiBXaGVuIHRoZSB0cmFuc3BvcnQgZW50ZXJzIGEgdG9sbCBzdGF0aW9uIHVuZGVyIHN1cnZlaWxsYW5jZSwgaXQgd2lsbCBiZSBjYXVnaHQgYnkgdGhlIHBvbGljZS48XC9wPlxyXG5cclxuPHA+RnJvbSB0aGlzIHBvaW50IG9mIHZpZXcsIHRoZSBlYXNpZXN0IGNob2ljZSB3b3VsZCBiZSB0byBwbGFjZSB0aGUgcG9saWNlIHNxdWFkIGVpdGhlciBhdCB0aGUgZW50cnkgcG9pbnQgb3IgdGhlIGV4aXQgcG9pbnQgb2YgdGhlIHRyYW5zcG9ydC4gSG93ZXZlciwgY29udHJvbGxpbmcgZWFjaCB0b2xsIHN0YXRpb24gaGFzIGEgY2VydGFpbiBjb3N0LCB3aGljaCBtYXkgdmFyeSBmcm9tIHN0YXRpb24gdG8gc3RhdGlvbi4gVGhlIHBvbGljZSB3YW50cyB0byBrZWVwIHRoZSBvdmVyYWxsIGNvc3QgYXMgbG93IGFzIHBvc3NpYmxlLCBzbyB0aGV5IG5lZWQgdG8gaWRlbnRpZnkgYSBtaW5pbWFsIGNvbnRyb2xsaW5nIHNldCBvZiB0b2xsIHN0YXRpb25zLCB3aGljaCBzYXRpc1x1ZmIwMWVzIHRoZSB0d28gY29uZGl0aW9uczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5hbGwgdHJhXHVmYjAzYyBmcm9tIHRoZSBoYXJib3VyIHRvIHRoZSB3YXJlaG91c2UgbXVzdCBwYXNzIHRocm91Z2ggYXQgbGVhc3Qgb25lIHN0YXRpb24gZnJvbSB0aGF0IHNldCw8XC9saT5cclxuXHQ8bGk+dGhlIGNvc3Qgb2YgbW9uaXRvcmluZyB0aGVzZSBzdGF0aW9ucyAoaS5lLiB0aGUgc3VtIG9mIHRoZWlyIGluZGl2aWR1YWwgbW9uaXRvcmluZyBjb3N0cykgaXMgbWluaW1hbC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Zb3UgbWF5IGFzc3VtZSB0aGF0IGl0IGlzIHBvc3NpYmxlIHRvIGdldCBmcm9tIHRoZSBoYXJib3VyIHRvIHRoZSB3YXJlaG91c2UgdXNpbmcgdGhlIGhpZ2h3YXlzLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0sIHRoYXQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+cmVhZHMgdGhlIGRlc2NyaXB0aW9uIG9mIHRoZSBoaWdod2F5IG5ldHdvcmssIHRoZSBtb25pdG9yaW5nIGNvc3RzIGFuZCB0aGUgbG9jYXRpb25zIG9mIHRoZSBlbnRyeSBhbmQgZXhpdCBwb2ludHMgb2YgdGhlIHRyYW5zcG9ydCBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCw8XC9saT5cclxuXHQ8bGk+XHVmYjAxbmRzIGEgbWluaW1hbCBjb250cm9sbGluZyBzZXQgb2YgdG9sbCBzdGF0aW9ucyw8XC9saT5cclxuXHQ8bGk+d3JpdGVzIHRoaXMgc2V0IHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIG4gYW5kIG0gKDIgJmxlOyBuICZsZTsgMjAwICwgMSAmbGU7IG0gJmxlOyAyMDAwMCkgJm1kYXNoOyB0aGUgbnVtYmVyIG9mIHRvbGwgc3RhdGlvbnMgYW5kIHRoZSBudW1iZXIgb2YgZGlyZWN0IGhpZ2h3YXkgc2VnbWVudHMuIFRoZSB0b2xsIHN0YXRpb25zIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gbi48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBhIGFuZCBiICgxICZsZTsgYSwgYiAmbGU7IG4sIGEgJm5lOyBiKSAmbWRhc2g7IHRoZSBudW1iZXJzIG9mIHRoZSB0b2xsIHN0YXRpb25zIGNsb3Nlc3QgdG8gdGhlIGhhcmJvdXIgYW5kIHRvIHRoZSB3YXJlaG91c2UsIHJlc3BlY3RpdmVseS48XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBuIGxpbmVzIGRlc2NyaWJlIHRoZSBtb25pdG9yaW5nIGNvc3RzLiBUaGUgaS10aCBvZiB0aGVzZSBsaW5lcyAoZm9yIDEgJmxlOyBpICZsZTsgbikgY29udGFpbnMgb25lIGludGVnZXIgJm1kYXNoOyB0aGUgbW9uaXRvcmluZyBjb3N0IG9mIHRoZSBpLXRoIHN0YXRpb24gKHdoaWNoIGlzIHBvc2l0aXZlIG51bWJlciBub3QgZXhjZWVkaW5nIDEwIDAwMCAwMDAgKS48XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBtIGxpbmVzIGRlc2NyaWJlIHRoZSBoaWdod2F5IG5ldHdvcmsuIFRoZSBqLXRoIG9mIHRoZXNlIGxpbmVzIChmb3IgMSAmbGU7IGogJmxlOyBtKSBjb250YWlucyB0d28gaW50ZWdlcnMgeCBhbmQgeSAoMSAmbGU7IHggJmx0OyB5ICZsZTsgbiksIGluZGljYXRpbmcgdGhhdCB0aGVyZSBpcyBhIGRpcmVjdCBoaWdod2F5IHNlZ21lbnQgYmV0d2VlbiB0b2xsIHN0YXRpb25zIG51bWJlcmVkIHggYW5kIHkuIEVhY2ggaGlnaHdheSBzZWdtZW50IGlzIGxpc3RlZCBvbmNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvbmx5IGxpbmUgb2YgdGhlIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgbnVtYmVycyBvZiB0b2xsIHN0YXRpb25zIGluIGEgbWluaW1hbCBjb250cm9sbGluZyBzZXQsIGdpdmVuIGluIGluY3JlYXNpbmcgb3JkZXIsIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLiBJZiB0aGVyZSBpcyBtb3JlIHRoYW4gb25lIG1pbmltYWwgY29udHJvbGxpbmcgc2V0LCB5b3VyIHByb2dyYW0gbWF5IG91dHB1dCBhbnlvbmUgb2YgdGhlbS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2008 6번

  • 문제를 번역한 사람: author4
  • 빠진 조건을 찾은 사람: HyehwA