시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 53 24 12 44.444%

문제

계속 앉아서 열심히 공부(?)만 하는 학생들은 운동량이 절대적으로 부족하다. 우리의 원장선생님은 이런 학생들을 불쌍히 여기시어 운동을 할 계획을 세우셨다. 그 운동은 바로 단체 릴레이 경주이다. 릴레이 경주란 다들 알다시피 1개의 baton을 가지고 서로 baton을 전달해 주며 달리는 경기이다.

N(N<=1,000,000)명의 학생들은 운동장으로 나와서 T(2<=T<=100)개의 구역에서 바톤을 받을 준비를 하고 있다. 구역과 구역사이는 무조건 1개의 길만 존재한다. 쉽게 말해서 그래프의 구조를 가지고 있다.

릴레이를 하기 위해 각각의 학생들은 구역에 서 있으며 어떤 구역에는 여러명의 사람들이 있을 수 있다. 또한 릴레이의 특성상 baton이 하나기 때문에 각 구역으로 이동하는 데는 1명만 이동할 수 있으며 1명의 학생은 1개의 구간만 달린다. 그래서 학생들은 구역에 적당이 서서 바톤을 받아 끝나는 지점 까지 도달하여야 한다. 그런데 학생들은 운동을 오래 하고 싶지 않아 한다. 그렇기 때문에 시작지점에서 끝나는 지점까지의 최단경로를 알고 싶어 한다. 학생들이 어느 구역에 배치 되어야 되는지 프로그램을 짜서 도와주자. 시작 지점에서 끝지점 까지 정확히 길이(거치는 간선의 수)가 N이 되는 최단경로의 길이를 구하자.

  • N명의 학생은 모두 달려야 한다.
  • 시작점이나 도착지점에서 학생들이 바톤을 기다릴 수는 있지만 끝날 때에는 마지막 학생이 도착구역으로 가야 한다.
  • 물론 사용한 길을 다시 갈 수도 있다.

입력

첫째 줄에 학생의 수 N(N<=1,000,000)과 구역의 수(T<=100) 시작지점의 번호S(1<=S<=1000) 도착지점의 번호 E(1<=E<=1000)가 주어진다. 그 다음 T개의 줄에 간선의 길이 L (1 ≤ L ≤ 1,000)과 간선을 잇는 두 점이 순서대로 주어진다. 참고로 번호는 1 2 3 4 순서대로 들어오지 않는다.

출력

첫째 줄에 최단경로의 길이를 구하라. 제한시간은 1초이다.

예제 입력 1

2 6 6 4
11 4 6
4 4 8
8 4 9
6 6 8
2 6 9
3 8 9

예제 출력 1

10

힌트

시작 지점이 6번과 8번에 학생이 서 기다리고 있으면 최단경로가 10이 된다. 6-9-8-4의 경로가 있지만 학생수가 2명 이기 때문에 우리가 원하는 경로가 아니다

W3sicHJvYmxlbV9pZCI6IjE3NDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZThcdWNjYjQgXHViOWI0XHViODA4XHVjNzc0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWFjYzRcdWMxOGQgXHVjNTQ5XHVjNTQ0XHVjMTFjIFx1YzVmNFx1YzJlY1x1ZDc4OCBcdWFjZjVcdWJkODAoPylcdWI5Y2MgXHVkNTU4XHViMjk0Jm5ic3A7XHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YzZiNFx1YjNkOVx1YjdjOVx1Yzc3NCBcdWM4MDhcdWIzMDBcdWM4MDFcdWM3M2NcdWI4NWMgXHViZDgwXHVjODcxXHVkNTU4XHViMmU0LiBcdWM2YjBcdWI5YWNcdWM3NTggXHVjNmQwXHVjN2E1XHVjMTIwXHVjMGRkXHViMmQ4XHVjNzQwIFx1Yzc3NFx1YjdmMCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDQgXHViZDg4XHVjMzBkXHVkNzg4IFx1YzVlY1x1YWUzMFx1YzJkY1x1YzViNCBcdWM2YjRcdWIzZDlcdWM3NDQgXHVkNTYwIFx1YWNjNFx1ZDY4ZFx1Yzc0NCBcdWMxMzhcdWM2YjBcdWMxNjhcdWIyZTQuJm5ic3A7XHVhZGY4IFx1YzZiNFx1YjNkOVx1Yzc0MCBcdWJjMTRcdWI4NWMgXHViMmU4XHVjY2I0IFx1YjliNFx1YjgwOFx1Yzc3NCBcdWFjYmRcdWM4ZmNcdWM3NzRcdWIyZTQuIFx1YjliNFx1YjgwOFx1Yzc3NCBcdWFjYmRcdWM4ZmNcdWI3ODAgXHViMmU0XHViNGU0IFx1YzU0Y1x1YjJlNFx1YzJkY1x1ZDUzYyAxXHVhYzFjXHVjNzU4IGJhdG9uXHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWMxMWNcdWI4NWMgYmF0b25cdWM3NDQgXHVjODA0XHViMmVjXHVkNTc0IFx1YzhmY1x1YmE3MCBcdWIyZWNcdWI5YWNcdWIyOTQgXHVhY2JkXHVhZTMwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5OKE4mbHQ7PTEsMDAwLDAwMClcdWJhODVcdWM3NTggXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YzZiNFx1YjNkOVx1YzdhNVx1YzczY1x1Yjg1YyBcdWIwOThcdWM2NDBcdWMxMWMgVCgyJmx0Oz1UJmx0Oz0xMDApXHVhYzFjXHVjNzU4IFx1YWQ2Y1x1YzVlZFx1YzVkMFx1YzExYyBcdWJjMTRcdWQxYTRcdWM3NDQgXHViYzFiXHVjNzQ0IFx1YzkwMFx1YmU0NFx1Yjk3YyBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWFkNmNcdWM1ZWRcdWFjZmMgXHVhZDZjXHVjNWVkXHVjMGFjXHVjNzc0XHViMjk0IFx1YmIzNFx1Yzg3MFx1YWM3NCAxXHVhYzFjXHVjNzU4IFx1YWUzOFx1YjljYyBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuIFx1YzI3ZFx1YWM4YyBcdWI5ZDBcdWQ1NzRcdWMxMWMgXHVhZGY4XHViNzk4XHVkNTA0XHVjNzU4IFx1YWQ2Y1x1Yzg3MFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5YjRcdWI4MDhcdWM3NzRcdWI5N2MgXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWFjMDFcdWFjMDFcdWM3NTggXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YWQ2Y1x1YzVlZFx1YzVkMCBcdWMxMWMgXHVjNzg4XHVjNzNjXHViYTcwIFx1YzViNFx1YjVhNCBcdWFkNmNcdWM1ZWRcdWM1ZDBcdWIyOTQgXHVjNWVjXHViN2VjXHViYTg1XHVjNzU4IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc3NCBcdWM3ODhcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHViNjEwXHVkNTVjIFx1YjliNFx1YjgwOFx1Yzc3NFx1Yzc1OCBcdWQyYjlcdWMxMzFcdWMwYzEgYmF0b25cdWM3NzQgXHVkNTU4XHViMDk4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWFjMDEgXHVhZDZjXHVjNWVkXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YjI5NCBcdWIzNzBcdWIyOTQgMVx1YmE4NVx1YjljYyBcdWM3NzRcdWIzZDlcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCAxXHViYTg1XHVjNzU4IFx1ZDU1OVx1YzBkZFx1Yzc0MCAxXHVhYzFjXHVjNzU4IFx1YWQ2Y1x1YWMwNFx1YjljYyBcdWIyZWNcdWI5YjBcdWIyZTQuIFx1YWRmOFx1Yjc5OFx1YzExYyBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgXHVhZDZjXHVjNWVkXHVjNWQwIFx1YzgwMVx1YjJmOVx1Yzc3NCBcdWMxMWNcdWMxMWMgXHViYzE0XHVkMWE0XHVjNzQ0IFx1YmMxYlx1YzU0NCBcdWIwNWRcdWIwOThcdWIyOTQgXHVjOWMwXHVjODEwIFx1YWU0Y1x1YzljMCBcdWIzYzRcdWIyZWNcdWQ1NThcdWM1ZWNcdWM1N2MgXHVkNTVjXHViMmU0LiZuYnNwO1x1YWRmOFx1YjdmMFx1YjM3MCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgXHVjNmI0XHViM2Q5XHVjNzQ0IFx1YzYyNFx1Yjc5OCBcdWQ1NThcdWFjZTAgXHVjMmY2XHVjOWMwIFx1YzU0YVx1YzU0NCBcdWQ1NWNcdWIyZTQuIFx1YWRmOFx1YjgwN1x1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjMmRjXHVjNzkxXHVjOWMwXHVjODEwXHVjNWQwXHVjMTFjIFx1YjA1ZFx1YjA5OFx1YjI5NCBcdWM5YzBcdWM4MTBcdWFlNGNcdWM5YzBcdWM3NTggXHVjZDVjXHViMmU4XHVhY2JkXHViODVjXHViOTdjIFx1YzU0Y1x1YWNlMCBcdWMyZjZcdWM1YjQgXHVkNTVjXHViMmU0LiZuYnNwO1x1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc3NCBcdWM1YjRcdWIyOTAgXHVhZDZjXHVjNWVkXHVjNWQwIFx1YmMzMFx1Y2U1OCBcdWI0MThcdWM1YjRcdWM1N2MgXHViNDE4XHViMjk0XHVjOWMwIFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM5ZGNcdWMxMWMgXHViM2M0XHVjNjQwXHVjOGZjXHVjNzkwLiBcdWMyZGNcdWM3OTEgXHVjOWMwXHVjODEwXHVjNWQwXHVjMTFjIFx1YjA1ZFx1YzljMFx1YzgxMCBcdWFlNGNcdWM5YzAgXHVjODE1XHVkNjU1XHVkNzg4IFx1YWUzOFx1Yzc3NChcdWFjNzBcdWNlNThcdWIyOTQgXHVhYzA0XHVjMTIwXHVjNzU4IFx1YzIxOClcdWFjMDAgTlx1Yzc3NCBcdWI0MThcdWIyOTQgXHVjZDVjXHViMmU4XHVhY2JkXHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+Tlx1YmE4NVx1Yzc1OCBcdWQ1NTlcdWMwZGRcdWM3NDAgXHViYWE4XHViNDUwIFx1YjJlY1x1YjgyNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzJkY1x1Yzc5MVx1YzgxMFx1Yzc3NFx1YjA5OCBcdWIzYzRcdWNjMjlcdWM5YzBcdWM4MTBcdWM1ZDBcdWMxMWMgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzc0IFx1YmMxNFx1ZDFhNFx1Yzc0NCBcdWFlMzBcdWIyZTRcdWI5YjQgXHVjMjE4XHViMjk0IFx1Yzc4OFx1YzljMFx1YjljYyBcdWIwNWRcdWIwYTAgXHViNTRjXHVjNWQwXHViMjk0IFx1YjljOFx1YzljMFx1YjljOSBcdWQ1NTlcdWMwZGRcdWM3NzQgXHViM2M0XHVjYzI5XHVhZDZjXHVjNWVkXHVjNzNjXHViODVjIFx1YWMwMFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YmIzY1x1Yjg2MCBcdWMwYWNcdWM2YTlcdWQ1NWMgXHVhZTM4XHVjNzQ0IFx1YjJlNFx1YzJkYyBcdWFjMDggXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQ1NTlcdWMwZGRcdWM3NTggXHVjMjE4IE4oTiZsdDs9MSwwMDAsMDAwKVx1YWNmYyBcdWFkNmNcdWM1ZWRcdWM3NTggXHVjMjE4KFQmbHQ7PTEwMCkgXHVjMmRjXHVjNzkxXHVjOWMwXHVjODEwXHVjNzU4IFx1YmM4OFx1ZDYzOFMoMSZsdDs9UyZsdDs9MTAwMCkgXHViM2M0XHVjYzI5XHVjOWMwXHVjODEwXHVjNzU4IFx1YmM4OFx1ZDYzOCBFKDEmbHQ7PUUmbHQ7PTEwMDApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDtcdWFkZjggXHViMmU0XHVjNzRjIFRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWFlMzhcdWM3NzQgTCAoMSAmbGU7IEwgJmxlOyAxLDAwMClcdWFjZmMgXHVhYzA0XHVjMTIwXHVjNzQ0IFx1Yzc4N1x1YjI5NCBcdWI0NTAgXHVjODEwXHVjNzc0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7XHVjYzM4XHVhY2UwXHViODVjIFx1YmM4OFx1ZDYzOFx1YjI5NCAxIDIgMyA0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWI0ZTRcdWM1YjRcdWM2MjRcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjZDVjXHViMmU4XHVhY2JkXHViODVjXHVjNzU4IFx1YWUzOFx1Yzc3NFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWI3N2MuIFx1YzgxY1x1ZDU1Y1x1YzJkY1x1YWMwNFx1Yzc0MCAxXHVjZDA4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWMyZGNcdWM3OTEgXHVjOWMwXHVjODEwXHVjNzc0IDZcdWJjODhcdWFjZmMgOFx1YmM4OFx1YzVkMCBcdWQ1NTlcdWMwZGRcdWM3NzQgXHVjMTFjIFx1YWUzMFx1YjJlNFx1YjlhY1x1YWNlMCBcdWM3ODhcdWM3M2NcdWJhNzQgXHVjZDVjXHViMmU4XHVhY2JkXHViODVjXHVhYzAwIDEwXHVjNzc0IFx1YjQxY1x1YjJlNC4gNi05LTgtNFx1Yzc1OCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjNzg4XHVjOWMwXHViOWNjIFx1ZDU1OVx1YzBkZFx1YzIxOFx1YWMwMCAyXHViYTg1IFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjNmIwXHViOWFjXHVhYzAwIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWFjYmRcdWI4NWNcdWFjMDAgXHVjNTQ0XHViMmM4XHViMmU0PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNzQ2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ293IFJlbGF5cyIsImRlc2NyaXB0aW9uIjoiPHA+Rm9yIHRoZWlyIHBoeXNpY2FsIGZpdG5lc3MgcHJvZ3JhbSwgTiAoMiAmbHQ7PSBOICZsdDs9IDEsMDAwLDAwMCkgY293cyBoYXZlIGRlY2lkZWQgdG8gcnVuIGEgcmVsYXkgcmFjZSB1c2luZyB0aGUgVCAoMiAmbHQ7PSBUICZsdDs9IDEwMCkgY293IHRyYWlscyB0aHJvdWdob3V0IHRoZSBwYXN0dXJlLjxcL3A+XHJcblxyXG48cD5FYWNoIHRyYWlsIGNvbm5lY3RzIHR3byBkaWZmZXJlbnQgaW50ZXJzZWN0aW9ucyAoMSAmbHQ7PSBJMV9pICZsdDs9IDEsMDAwOyAxICZsdDs9IEkyX2kgJmx0Oz0gMSwwMDApLCBlYWNoIG9mIHdoaWNoIGlzIHRoZSB0ZXJtaW5hdGlvbiBmb3IgYXQgbGVhc3QgdHdvIHRyYWlscy4gVGhlIGNvd3Mga25vdyB0aGUgbGVuZ3RoX2kgb2YgZWFjaCB0cmFpbCAoMSAmbHQ7PSBsZW5ndGhfaSAmbHQ7PSAxLDAwMCksIHRoZSB0d28gaW50ZXJzZWN0aW9ucyB0aGUgdHJhaWwgY29ubmVjdHMsIGFuZCB0aGV5IGtub3cgdGhhdCBubyB0d28gaW50ZXJzZWN0aW9ucyBhcmUgZGlyZWN0bHkgY29ubmVjdGVkIGJ5IHR3byBkaWZmZXJlbnQgdHJhaWxzLiBUaGUgdHJhaWxzIGZvcm0gYSBzdHJ1Y3R1cmUga25vd24gbWF0aGVtYXRpY2FsbHkgYXMgYSBncmFwaC48XC9wPlxyXG5cclxuPHA+VG8gcnVuIHRoZSByZWxheSwgdGhlIE4gY293cyBwb3NpdGlvbiB0aGVtc2VsdmVzIGF0IHZhcmlvdXMgaW50ZXJzZWN0aW9ucyAoc29tZSBpbnRlcnNlY3Rpb25zIG1pZ2h0IGhhdmUgbW9yZSB0aGFuIG9uZSBjb3cpLiBUaGV5IG11c3QgcG9zaXRpb24gdGhlbXNlbHZlcyBwcm9wZXJseSBzbyB0aGF0IHRoZXkgY2FuIGhhbmQgb2ZmIHRoZSBiYXRvbiBjb3ctYnktY293IGFuZCBlbmQgdXAgYXQgdGhlIHByb3BlciBmaW5pc2hpbmcgcGxhY2UuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0byBoZWxwIHBvc2l0aW9uIHRoZSBjb3dzLiBGaW5kIHRoZSBzaG9ydGVzdCBwYXRoIHRoYXQgY29ubmVjdHMgdGhlIHN0YXJ0aW5nIGludGVyc2VjdGlvbiAoUykgYW5kIHRoZSBlbmRpbmcgaW50ZXJzZWN0aW9uIChFKSBhbmQgdHJhdmVyc2VzIGV4YWN0bHkgTiBjb3cgdHJhaWxzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+KiBMaW5lIDE6IEZvdXIgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBOLCBULCBTLCBhbmQgRTxcL3A+XHJcblxyXG48cD4qIExpbmVzIDIuLlQrMTogTGluZSBpKzEgZGVzY3JpYmVzIHRyYWlsIGkgd2l0aCB0aHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IGxlbmd0aF9pLCBJMV9pLCBhbmQgSTJfaTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiogTGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyIHRoYXQgaXMgdGhlIHNob3J0ZXN0IGRpc3RhbmNlIGZyb20gaW50ZXJzZWN0aW9uIFMgdG8gaW50ZXJzZWN0aW9uIEUgdGhhdCB0cmF2ZXJzZXMgZXhhY3RseSBOIGNvdyB0cmFpbHMuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 2007-2008 Season > USACO November 2007 Contest > Gold 2번