시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 561 132 93 20.130%

문제

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

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

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

입력

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

출력

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

예제 입력 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+XHJcblxyXG48cD5cdWM1YjRcdWIyOTAgXHViMGEwIFx1YWRmOFx1YjI5NCBcdWFkZjhcdWFjMDAgXHVhYzEwXHVjMmRjXHViOTdjIFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyOTQgXHViOWM4XHVkNTNjXHVjNTQ0IFx1Yzg3MFx1YzljMVx1YzVkMFx1YzExYyBcdWIzMDBcdWFkZGNcdWJhYTggXHVjNzc0XHViM2Q5XHVjNzc0IFx1Yzc4OFx1Yzc0Y1x1Yzc0NCBcdWFjMTBcdWM5YzBcdWQ1ODhcdWIyZTQuIFx1YjljOFx1ZDUzY1x1YzU0NFx1YjI5NCBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWI5N2MgXHVkMWI1XHVkNTc0XHVjMTFjIFx1Yzc3NFx1YjNkOVx1Yzc0NCBcdWQ1NThcdWIyOTRcdWIzNzAgXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHViOWRkXHVjNzQwIG5cdWFjMWNcdWM3NTggXHVkMWE4XHVhYzhjXHVjNzc0XHVkMmI4XHVjNjQwIFx1YWRmOCBcdWMwYWNcdWM3NzRcdWI5N2MgXHVjNzg4XHViMjk0IG1cdWFjMWNcdWM3NTggXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOFx1Yzc4OFx1YjJlNC4gXHVhY2UwXHVjMThkXHViM2M0XHViODVjXHVjNzU4IFx1YzkxMVx1YWMwNFx1YzVkMFx1YzExYyBcdWJjMTZcdWM3M2NcdWI4NWMgXHViMDk4XHVhYzAwXHVhYzcwXHViMDk4IFx1YzkxMVx1YWMwNFx1YzczY1x1Yjg1YyBcdWI0ZTRcdWM1YjRcdWM2MjRcdWM5YzBcdWIyOTQgXHViYWJiXHVkNTVjXHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MC4gXHVjOTg5IFx1YmFhOFx1YjRlMCBcdWM3NzRcdWIzZDlcdWM3NDAgXHVkMWE4XHVhYzhjXHVjNzc0XHVkMmI4XHVjNjQwIFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWFjNzBcdWNjZDBcdWMxMWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4XHVjNTdjIFx1YjQxY1x1YjJlNFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjljOFx1ZDUzY1x1YzU0NFx1Yzc1OCBcdWMyZGNcdWM3OTFcdWM4MTBcdWFjZmMgXHViM2M0XHVjYzI5XHVjODEwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljOCBcdWI1NGMgXHVjNmIwXHViOWFjXHViMjk0IFx1YmE4NyBcdWFjMWNcdWM3NTggXHVkMWE4XHVhYzhjXHVjNzc0XHVkMmI4XHViOTdjIFx1YzgxMFx1YWM3MFx1ZDU3NFx1YzExYyBcdWI5YzhcdWQ1M2NcdWM1NDRcdWFjMDAgXHVjMmRjXHVjNzkxXHVjODEwXHVjNWQwXHVjMTFjIFx1YjNjNFx1Y2MyOVx1YzgxMFx1YWU0Y1x1YzljMCBcdWM2YjBcdWI5YWNcdWM3NTggXHVjODEwXHVhYzcwXHViNDFjIFx1ZDFhOFx1YWM4Y1x1Yzc3NFx1ZDJiOFx1Yjk3YyBcdWM5YzBcdWIwOThcdWM5YzAgXHVjNTRhXHVhY2UwXHVjMTFjXHViMjk0IFx1YjNjNFx1Y2MyOVx1ZDU2MCBcdWMyMTggXHVjNWM2XHVhYzhjIFx1ZDU1OFx1YWNlMCBcdWMyZjZcdWIyZTQuIFx1YWRmOFx1YjdmMFx1YjM3MCBcdWQxYThcdWFjOGNcdWM3NzRcdWQyYjhcdWI5N2MgXHVjODEwXHVhYzcwXHVkNTU4XHViMjk0XHViMzcwXHVjNWQwXHViMjk0IFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxYThcdWFjOGNcdWM3NzRcdWQyYjhcdWI5YzhcdWIyZTQgXHVhY2UwXHVjNzIwXHVkNTVjIFx1YmU0NFx1YzZhOVx1Yzc3NCBcdWI0ZTBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjU0YyBcdWM4MTBcdWFjNzBcdWJlNDRcdWI5N2MgXHVjZDVjXHVjMThjXHVkNjU0IFx1ZDU1OFx1YmE3MCBcdWI5YzhcdWQ1M2NcdWM1NDRcdWM3NTggXHVjNmMwXHVjOWMxXHVjNzg0XHVjNzQ0IFx1YjljOVx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjODEwXHVhYzcwXHVkNTc0XHVjNTdjXHViNDE4XHViMjk0IFx1YjNjNFx1YzJkY1x1YjRlNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDFhOFx1YWM4Y1x1Yzc3NFx1ZDJiOFx1Yzc1OCBcdWFjMWNcdWMyMTggblx1YWNmYyBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWM3NTggXHVhYzFjXHVjMjE4IG1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LigxICZsZTsmbmJzcDtuICZsZTsgMjAwLCAxICZsZTsgbSAmbGU7IDIwMDAwKSBcdWQxYThcdWFjOGNcdWM3NzRcdWQyYjhcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IDFcdWJkODBcdWQxMzAgblx1YWU0Y1x1YzljMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTRcdWFjZTAgXHVkNTYwIFx1YjU0YywgXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI5YzhcdWQ1M2NcdWM1NDRcdWM3NTggXHVjMmRjXHVjNzkxXHVjODEwXHVhY2ZjIFx1YjNjNFx1Y2MyOVx1YzgxMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFkZjggXHViMmU0XHVjNzRjIG5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWQxYThcdWFjOGNcdWM3NzRcdWQyYjhcdWJjYzQgXHVjODEwXHVhYzcwXHViZTQ0XHVjNmE5XHVjNzc0IFx1YjA5OFx1YzYyOFx1YjJlNC4gXHVhZGY4IFx1YjRhNCBtXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxYThcdWFjOGNcdWM3NzRcdWQyYjhcdWI5N2MgXHVjNzg3XHViMjk0IFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1YjRlNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7XHVjODEwXHVhYzcwXHViZTQ0XHVjNmE5XHVjNzQwJm5ic3A7MTAsMDAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWM4MTBcdWFjNzBcdWJlNDRcdWI5N2MgXHVjZDVjXHVjMThjXHVkNjU0IFx1ZDU1OFx1YmE3MCBcdWI5YzhcdWQ1M2NcdWM1NDRcdWM3NTggXHVjNmMwXHVjOWMxXHVjNzg0XHVjNzQ0IFx1YjljOVx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjODEwXHVhYzcwXHVkNTc0XHVjNTdjXHViNDE4XHViMjk0IFx1YjNjNFx1YzJkY1x1YjRlNFx1Yzc0NCBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjZDljXHViODI1XHVkNTU4XHVjNWVjXHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEyMTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNYWZpYSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIHBvbGljZSBpbiBCeXRlbGFuZCBnb3QgYW4gYW5vbnltb3VzIHRpcCB0aGF0IHRoZSBsb2NhbCBtYVx1ZmIwMWEgYm9zc2VzIGFyZSBwbGFubmluZyBhIGJpZyB0cmFuc3BvcnQgZnJvbSB0aGUgaGFyYm91ciB0byBvbmUgb2YgdGhlIHNlY3JldCB3YXJlaG91c2VzIGluIHRoZSBjb3VudHJ5c2lkZS4gVGhlIHBvbGljZSBrbm93cyB0aGUgZGF0ZSBvZiB0aGUgdHJhbnNwb3J0IGFuZCB0aGV5IGtub3cgdGhhdCB0aGUgdHJhbnNwb3J0IHdpbGwgdXNlIHRoZSBuYXRpb25hbCBoaWdod2F5IG5ldHdvcmsuPFwvcD5cclxuXHJcbjxwPlRoZSBoaWdod2F5IG5ldHdvcmsgY29uc2lzdHMgb2YgdHdvLXdheSBoaWdod2F5IHNlZ21lbnRzLCBlYWNoIHNlZ21lbnQgZGlyZWN0bHkgY29ubmVjdGluZyB0d28gZGlzdGluY3QgdG9sbCBzdGF0aW9ucy4gQSB0b2xsIHN0YXRpb24gbWF5IGJlIGNvbm5lY3RlZCB3aXRoIG1hbnkgb3RoZXIgc3RhdGlvbnMuIEEgdmVoaWNsZSBjYW4gZW50ZXIgb3IgZXhpdCB0aGUgaGlnaHdheSBuZXR3b3JrIGF0IHRvbGwgc3RhdGlvbnMgb25seS4gVGhlIG1hXHVmYjAxYSB0cmFuc3BvcnQgaXMga25vd24gdG8gZW50ZXIgdGhlIGhpZ2h3YXlzIGF0IHRoZSB0b2xsIHN0YXRpb24gY2xvc2VzdCB0byB0aGUgaGFyYm91ciBhbmQgbGVhdmUgaXQgYXQgdGhlIHRvbGwgc3RhdGlvbiBjbG9zZXN0IHRvIHRoZSB3YXJlaG91c2UgKGl0IHdpbGwgbm90IGxlYXZlIGFuZCByZS1lbnRlciB0aGUgaGlnaHdheXMgaW4gYmV0d2VlbikuIFNwZWNpYWwgcG9saWNlIHNxdWFkcyBhcmUgdG8gYmUgbG9jYXRlZCBpbiBzZWxlY3RlZCB0b2xsIHN0YXRpb25zLiBXaGVuIHRoZSB0cmFuc3BvcnQgZW50ZXJzIGEgdG9sbCBzdGF0aW9uIHVuZGVyIHN1cnZlaWxsYW5jZSwgaXQgd2lsbCBiZSBjYXVnaHQgYnkgdGhlIHBvbGljZS48XC9wPlxyXG5cclxuPHA+RnJvbSB0aGlzIHBvaW50IG9mIHZpZXcsIHRoZSBlYXNpZXN0IGNob2ljZSB3b3VsZCBiZSB0byBwbGFjZSB0aGUgcG9saWNlIHNxdWFkIGVpdGhlciBhdCB0aGUgZW50cnkgcG9pbnQgb3IgdGhlIGV4aXQgcG9pbnQgb2YgdGhlIHRyYW5zcG9ydC4gSG93ZXZlciwgY29udHJvbGxpbmcgZWFjaCB0b2xsIHN0YXRpb24gaGFzIGEgY2VydGFpbiBjb3N0LCB3aGljaCBtYXkgdmFyeSBmcm9tIHN0YXRpb24gdG8gc3RhdGlvbi4gVGhlIHBvbGljZSB3YW50cyB0byBrZWVwIHRoZSBvdmVyYWxsIGNvc3QgYXMgbG93IGFzIHBvc3NpYmxlLCBzbyB0aGV5IG5lZWQgdG8gaWRlbnRpZnkgYSBtaW5pbWFsIGNvbnRyb2xsaW5nIHNldCBvZiB0b2xsIHN0YXRpb25zLCB3aGljaCBzYXRpc1x1ZmIwMWVzIHRoZSB0d28gY29uZGl0aW9uczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5hbGwgdHJhXHVmYjAzYyBmcm9tIHRoZSBoYXJib3VyIHRvIHRoZSB3YXJlaG91c2UgbXVzdCBwYXNzIHRocm91Z2ggYXQgbGVhc3Qgb25lIHN0YXRpb24gZnJvbSB0aGF0IHNldCw8XC9saT5cclxuXHQ8bGk+dGhlIGNvc3Qgb2YgbW9uaXRvcmluZyB0aGVzZSBzdGF0aW9ucyAoaS5lLiB0aGUgc3VtIG9mIHRoZWlyIGluZGl2aWR1YWwgbW9uaXRvcmluZyBjb3N0cykgaXMgbWluaW1hbC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5Zb3UgbWF5IGFzc3VtZSB0aGF0IGl0IGlzIHBvc3NpYmxlIHRvIGdldCBmcm9tIHRoZSBoYXJib3VyIHRvIHRoZSB3YXJlaG91c2UgdXNpbmcgdGhlIGhpZ2h3YXlzLjxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0sIHRoYXQ6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+cmVhZHMgdGhlIGRlc2NyaXB0aW9uIG9mIHRoZSBoaWdod2F5IG5ldHdvcmssIHRoZSBtb25pdG9yaW5nIGNvc3RzIGFuZCB0aGUgbG9jYXRpb25zIG9mIHRoZSBlbnRyeSBhbmQgZXhpdCBwb2ludHMgb2YgdGhlIHRyYW5zcG9ydCBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCw8XC9saT5cclxuXHQ8bGk+XHVmYjAxbmRzIGEgbWluaW1hbCBjb250cm9sbGluZyBzZXQgb2YgdG9sbCBzdGF0aW9ucyw8XC9saT5cclxuXHQ8bGk+d3JpdGVzIHRoaXMgc2V0IHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBcdWZiMDFyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIG4gYW5kIG0gKDIgJmxlOyBuICZsZTsgMjAwICwgMSAmbGU7IG0gJmxlOyAyMDAwMCkgJm1kYXNoOyB0aGUgbnVtYmVyIG9mIHRvbGwgc3RhdGlvbnMgYW5kIHRoZSBudW1iZXIgb2YgZGlyZWN0IGhpZ2h3YXkgc2VnbWVudHMuIFRoZSB0b2xsIHN0YXRpb25zIGFyZSBudW1iZXJlZCBmcm9tIDEgdG8gbi48XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBhIGFuZCBiICgxICZsZTsgYSwgYiAmbGU7IG4sIGEgJm5lOyBiKSAmbWRhc2g7IHRoZSBudW1iZXJzIG9mIHRoZSB0b2xsIHN0YXRpb25zIGNsb3Nlc3QgdG8gdGhlIGhhcmJvdXIgYW5kIHRvIHRoZSB3YXJlaG91c2UsIHJlc3BlY3RpdmVseS48XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBuIGxpbmVzIGRlc2NyaWJlIHRoZSBtb25pdG9yaW5nIGNvc3RzLiBUaGUgaS10aCBvZiB0aGVzZSBsaW5lcyAoZm9yIDEgJmxlOyBpICZsZTsgbikgY29udGFpbnMgb25lIGludGVnZXIgJm1kYXNoOyB0aGUgbW9uaXRvcmluZyBjb3N0IG9mIHRoZSBpLXRoIHN0YXRpb24gKHdoaWNoIGlzIHBvc2l0aXZlIG51bWJlciBub3QgZXhjZWVkaW5nIDEwIDAwMCAwMDAgKS48XC9wPlxyXG5cclxuPHA+VGhlIGZvbGxvd2luZyBtIGxpbmVzIGRlc2NyaWJlIHRoZSBoaWdod2F5IG5ldHdvcmsuIFRoZSBqLXRoIG9mIHRoZXNlIGxpbmVzIChmb3IgMSAmbGU7IGogJmxlOyBtKSBjb250YWlucyB0d28gaW50ZWdlcnMgeCBhbmQgeSAoMSAmbGU7IHggJmx0OyB5ICZsZTsgbiksIGluZGljYXRpbmcgdGhhdCB0aGVyZSBpcyBhIGRpcmVjdCBoaWdod2F5IHNlZ21lbnQgYmV0d2VlbiB0b2xsIHN0YXRpb25zIG51bWJlcmVkIHggYW5kIHkuIEVhY2ggaGlnaHdheSBzZWdtZW50IGlzIGxpc3RlZCBvbmNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvbmx5IGxpbmUgb2YgdGhlIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgbnVtYmVycyBvZiB0b2xsIHN0YXRpb25zIGluIGEgbWluaW1hbCBjb250cm9sbGluZyBzZXQsIGdpdmVuIGluIGluY3JlYXNpbmcgb3JkZXIsIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzLiBJZiB0aGVyZSBpcyBtb3JlIHRoYW4gb25lIG1pbmltYWwgY29udHJvbGxpbmcgc2V0LCB5b3VyIHByb2dyYW0gbWF5IG91dHB1dCBhbnlvbmUgb2YgdGhlbS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2008 6번