시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB73332047.619%

문제

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

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

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

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

입력

첫째 줄에 학생의 수 N(2 ≤ N ≤ 1,000,000)과 구역의 수(2 ≤ 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

예제 입력 2

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

예제 출력 2

30

힌트

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

W3sicHJvYmxlbV9pZCI6IjE3NDYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZThcdWNjYjQgXHViOWI0XHViODA4XHVjNzc0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWFjYzRcdWMxOGQgXHVjNTQ5XHVjNTQ0XHVjMTFjIFx1YzVmNFx1YzJlY1x1ZDc4OCBcdWFjZjVcdWJkODAoPylcdWI5Y2MgXHVkNTU4XHViMjk0Jm5ic3A7XHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YzZiNFx1YjNkOVx1YjdjOVx1Yzc3NCBcdWM4MDhcdWIzMDBcdWM4MDFcdWM3M2NcdWI4NWMgXHViZDgwXHVjODcxXHVkNTU4XHViMmU0LiBcdWM2YjBcdWI5YWNcdWM3NTggXHVjNmQwXHVjN2E1XHVjMTIwXHVjMGRkXHViMmQ4XHVjNzQwIFx1Yzc3NFx1YjdmMCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDQgXHViZDg4XHVjMzBkXHVkNzg4IFx1YzVlY1x1YWUzMFx1YzJkY1x1YzViNCBcdWM2YjRcdWIzZDlcdWM3NDQgXHVkNTYwIFx1YWNjNFx1ZDY4ZFx1Yzc0NCBcdWMxMzhcdWM2YjBcdWMxNjhcdWIyZTQuJm5ic3A7XHVhZGY4IFx1YzZiNFx1YjNkOVx1Yzc0MCBcdWJjMTRcdWI4NWMgXHViMmU4XHVjY2I0IFx1YjliNFx1YjgwOFx1Yzc3NCBcdWFjYmRcdWM4ZmNcdWM3NzRcdWIyZTQuIFx1YjliNFx1YjgwOFx1Yzc3NCBcdWFjYmRcdWM4ZmNcdWI3ODAgXHViMmU0XHViNGU0IFx1YzU0Y1x1YjJlNFx1YzJkY1x1ZDUzYyAxXHVhYzFjXHVjNzU4IGJhdG9uXHVjNzQ0IFx1YWMwMFx1YzljMFx1YWNlMCBcdWMxMWNcdWI4NWMgYmF0b25cdWM3NDQgXHVjODA0XHViMmVjXHVkNTc0IFx1YzhmY1x1YmE3MCBcdWIyZWNcdWI5YWNcdWIyOTQgXHVhY2JkXHVhZTMwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5OKDIgJmxlOyBOICZsZTsgMSwwMDAsMDAwKVx1YmE4NVx1Yzc1OCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDAgXHVjNmI0XHViM2Q5XHVjN2E1XHVjNzNjXHViODVjIFx1YjA5OFx1YzY0MFx1YzExYyBUKDIgJmxlOyBUICZsZTsgMTAwKVx1YWMxY1x1Yzc1OCBcdWFkNmNcdWM1ZWRcdWM1ZDBcdWMxMWMgXHViYzE0XHVkMWE0XHVjNzQ0IFx1YmMxYlx1Yzc0NCBcdWM5MDBcdWJlNDRcdWI5N2MgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhZDZjXHVjNWVkXHVhY2ZjIFx1YWQ2Y1x1YzVlZFx1YzBhY1x1Yzc3NFx1YjI5NCBcdWJiMzRcdWM4NzBcdWFjNzQgMVx1YWMxY1x1Yzc1OCBcdWFlMzhcdWI5Y2MgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LiBcdWMyN2RcdWFjOGMgXHViOWQwXHVkNTc0XHVjMTFjIFx1YWRmOFx1Yjc5OFx1ZDUwNFx1Yzc1OCBcdWFkNmNcdWM4NzBcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWI0XHViODA4XHVjNzc0XHViOTdjIFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWFkNmNcdWM1ZWRcdWM1ZDAgXHVjMTFjIFx1Yzc4OFx1YzczY1x1YmE3MCBcdWM1YjRcdWI1YTQgXHVhZDZjXHVjNWVkXHVjNWQwXHViMjk0IFx1YzVlY1x1YjdlY1x1YmE4NVx1Yzc1OCBcdWMwYWNcdWI3OGNcdWI0ZTRcdWM3NzQgXHVjNzg4XHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjYxMFx1ZDU1YyBcdWI5YjRcdWI4MDhcdWM3NzRcdWM3NTggXHVkMmI5XHVjMTMxXHVjMGMxIGJhdG9uXHVjNzc0IFx1ZDU1OFx1YjA5OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVhYzAxIFx1YWQ2Y1x1YzVlZFx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWIyOTQgXHViMzcwXHViMjk0IDFcdWJhODVcdWI5Y2MgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWM3M2NcdWJhNzAgMVx1YmE4NVx1Yzc1OCBcdWQ1NTlcdWMwZGRcdWM3NDAgMVx1YWMxY1x1Yzc1OCBcdWFkNmNcdWFjMDRcdWI5Y2MgXHViMmVjXHViOWIwXHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YWQ2Y1x1YzVlZFx1YzVkMCBcdWM4MDFcdWIyZjlcdWM3NzQgXHVjMTFjXHVjMTFjIFx1YmMxNFx1ZDFhNFx1Yzc0NCBcdWJjMWJcdWM1NDQgXHViMDVkXHViMDk4XHViMjk0IFx1YzljMFx1YzgxMCBcdWFlNGNcdWM5YzAgXHViM2M0XHViMmVjXHVkNTU4XHVjNWVjXHVjNTdjIFx1ZDU1Y1x1YjJlNC4mbmJzcDtcdWFkZjhcdWI3ZjBcdWIzNzAgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1YzZiNFx1YjNkOVx1Yzc0NCBcdWM2MjRcdWI3OTggXHVkNTU4XHVhY2UwIFx1YzJmNlx1YzljMCBcdWM1NGFcdWM1NDQgXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI4MDdcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1YzJkY1x1Yzc5MVx1YzljMFx1YzgxMFx1YzVkMFx1YzExYyBcdWIwNWRcdWIwOThcdWIyOTQgXHVjOWMwXHVjODEwXHVhZTRjXHVjOWMwXHVjNzU4IFx1Y2Q1Y1x1YjJlOFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWM1NGNcdWFjZTAgXHVjMmY2XHVjNWI0IFx1ZDU1Y1x1YjJlNC4mbmJzcDtcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NzQgXHVjNWI0XHViMjkwIFx1YWQ2Y1x1YzVlZFx1YzVkMCBcdWJjMzBcdWNlNTggXHViNDE4XHVjNWI0XHVjNTdjIFx1YjQxOFx1YjI5NFx1YzljMCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjOWRjXHVjMTFjIFx1YjNjNFx1YzY0MFx1YzhmY1x1Yzc5MC4gXHVjMmRjXHVjNzkxIFx1YzljMFx1YzgxMFx1YzVkMFx1YzExYyBcdWIwNWRcdWM5YzBcdWM4MTAgXHVhZTRjXHVjOWMwIFx1YzgxNVx1ZDY1NVx1ZDc4OCBcdWFlMzhcdWM3NzQoXHVhYzcwXHVjZTU4XHViMjk0IFx1YWMwNFx1YzEyMFx1Yzc1OCBcdWMyMTgpXHVhYzAwIE5cdWM3NzQgXHViNDE4XHViMjk0IFx1Y2Q1Y1x1YjJlOFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVhZDZjXHVkNTU4XHVjNzkwLjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk5cdWJhODVcdWM3NTggXHVkNTU5XHVjMGRkXHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWIyZWNcdWI4MjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWMyZGNcdWM3OTFcdWM4MTBcdWM3NzRcdWIwOTggXHViM2M0XHVjYzI5XHVjOWMwXHVjODEwXHVjNWQwXHVjMTFjIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc3NCBcdWJjMTRcdWQxYTRcdWM3NDQgXHVhZTMwXHViMmU0XHViOWI0IFx1YzIxOFx1YjI5NCBcdWM3ODhcdWM5YzBcdWI5Y2MgXHViMDVkXHViMGEwIFx1YjU0Y1x1YzVkMFx1YjI5NCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVkNTU5XHVjMGRkXHVjNzc0IFx1YjNjNFx1Y2MyOVx1YWQ2Y1x1YzVlZFx1YzczY1x1Yjg1YyBcdWFjMDBcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWJiM2NcdWI4NjAgXHVjMGFjXHVjNmE5XHVkNTVjIFx1YWUzOFx1Yzc0NCBcdWIyZTRcdWMyZGMgXHVhYzA4IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkNTU5XHVjMGRkXHVjNzU4IFx1YzIxOCBOKDIgJmxlOyBOICZsZTsgMSwwMDAsMDAwKVx1YWNmYyBcdWFkNmNcdWM1ZWRcdWM3NTggXHVjMjE4KDIgJmxlOyBUICZsZTsgMTAwKSBcdWMyZGNcdWM3OTFcdWM5YzBcdWM4MTBcdWM3NTggXHViYzg4XHVkNjM4IFMoMSAmbGU7IFMgJmxlOyAxMDAwKSBcdWIzYzRcdWNjMjlcdWM5YzBcdWM4MTBcdWM3NTggXHViYzg4XHVkNjM4IEUoMSAmbGU7IEUgJmxlOyAxMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7XHVhZGY4IFx1YjJlNFx1Yzc0YyBUXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjMDRcdWMxMjBcdWM3NTggXHVhZTM4XHVjNzc0IEwgKDEgJmxlOyBMICZsZTsgMSwwMDApXHVhY2ZjIFx1YWMwNFx1YzEyMFx1Yzc0NCBcdWM3ODdcdWIyOTQgXHViNDUwIFx1YzgxMFx1Yzc3NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwO1x1Y2MzOFx1YWNlMFx1Yjg1YyBcdWJjODhcdWQ2MzhcdWIyOTQgMSAyIDMgNCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHViNGU0XHVjNWI0XHVjNjI0XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2Q1Y1x1YjJlOFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVhZDZjXHVkNTU4XHViNzdjLiBcdWM4MWNcdWQ1NWNcdWMyZGNcdWFjMDRcdWM3NDAgMVx1Y2QwOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjNjA4XHVjODFjIDFcdWM3NTggXHVhY2JkXHVjNmIwIFx1YzJkY1x1Yzc5MSBcdWM5YzBcdWM4MTBcdWM3NzQgNlx1YmM4OFx1YWNmYyA4XHViYzg4XHVjNWQwIFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWMxMWMgXHVhZTMwXHViMmU0XHViOWFjXHVhY2UwIFx1Yzc4OFx1YzczY1x1YmE3NCBcdWNkNWNcdWIyZThcdWFjYmRcdWI4NWNcdWFjMDAgMTBcdWM3NzQgXHViNDFjXHViMmU0LiA2LTktOC00XHVjNzU4IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWM5YzBcdWI5Y2MgXHVkNTU5XHVjMGRkXHVjMjE4XHVhYzAwIDJcdWJhODUgXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM2YjBcdWI5YWNcdWFjMDAgXHVjNmQwXHVkNTU4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWM1NDRcdWIyYzhcdWIyZTQ8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjE3NDYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb3cgUmVsYXlzIiwiZGVzY3JpcHRpb24iOiI8cD5Gb3IgdGhlaXIgcGh5c2ljYWwgZml0bmVzcyBwcm9ncmFtLCBOICgyICZsdDs9IE4gJmx0Oz0gMSwwMDAsMDAwKSBjb3dzIGhhdmUgZGVjaWRlZCB0byBydW4gYSByZWxheSByYWNlIHVzaW5nIHRoZSBUICgyICZsdDs9IFQgJmx0Oz0gMTAwKSBjb3cgdHJhaWxzIHRocm91Z2hvdXQgdGhlIHBhc3R1cmUuPFwvcD5cclxuXHJcbjxwPkVhY2ggdHJhaWwgY29ubmVjdHMgdHdvIGRpZmZlcmVudCBpbnRlcnNlY3Rpb25zICgxICZsdDs9IEkxX2kgJmx0Oz0gMSwwMDA7IDEgJmx0Oz0gSTJfaSAmbHQ7PSAxLDAwMCksIGVhY2ggb2Ygd2hpY2ggaXMgdGhlIHRlcm1pbmF0aW9uIGZvciBhdCBsZWFzdCB0d28gdHJhaWxzLiBUaGUgY293cyBrbm93IHRoZSBsZW5ndGhfaSBvZiBlYWNoIHRyYWlsICgxICZsdDs9IGxlbmd0aF9pICZsdDs9IDEsMDAwKSwgdGhlIHR3byBpbnRlcnNlY3Rpb25zIHRoZSB0cmFpbCBjb25uZWN0cywgYW5kIHRoZXkga25vdyB0aGF0IG5vIHR3byBpbnRlcnNlY3Rpb25zIGFyZSBkaXJlY3RseSBjb25uZWN0ZWQgYnkgdHdvIGRpZmZlcmVudCB0cmFpbHMuIFRoZSB0cmFpbHMgZm9ybSBhIHN0cnVjdHVyZSBrbm93biBtYXRoZW1hdGljYWxseSBhcyBhIGdyYXBoLjxcL3A+XHJcblxyXG48cD5UbyBydW4gdGhlIHJlbGF5LCB0aGUgTiBjb3dzIHBvc2l0aW9uIHRoZW1zZWx2ZXMgYXQgdmFyaW91cyBpbnRlcnNlY3Rpb25zIChzb21lIGludGVyc2VjdGlvbnMgbWlnaHQgaGF2ZSBtb3JlIHRoYW4gb25lIGNvdykuIFRoZXkgbXVzdCBwb3NpdGlvbiB0aGVtc2VsdmVzIHByb3Blcmx5IHNvIHRoYXQgdGhleSBjYW4gaGFuZCBvZmYgdGhlIGJhdG9uIGNvdy1ieS1jb3cgYW5kIGVuZCB1cCBhdCB0aGUgcHJvcGVyIGZpbmlzaGluZyBwbGFjZS48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRvIGhlbHAgcG9zaXRpb24gdGhlIGNvd3MuIEZpbmQgdGhlIHNob3J0ZXN0IHBhdGggdGhhdCBjb25uZWN0cyB0aGUgc3RhcnRpbmcgaW50ZXJzZWN0aW9uIChTKSBhbmQgdGhlIGVuZGluZyBpbnRlcnNlY3Rpb24gKEUpIGFuZCB0cmF2ZXJzZXMgZXhhY3RseSBOIGNvdyB0cmFpbHMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD4qIExpbmUgMTogRm91ciBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IE4sIFQsIFMsIGFuZCBFPFwvcD5cclxuXHJcbjxwPiogTGluZXMgMi4uVCsxOiBMaW5lIGkrMSBkZXNjcmliZXMgdHJhaWwgaSB3aXRoIHRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogbGVuZ3RoX2ksIEkxX2ksIGFuZCBJMl9pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+KiBMaW5lIDE6IEEgc2luZ2xlIGludGVnZXIgdGhhdCBpcyB0aGUgc2hvcnRlc3QgZGlzdGFuY2UgZnJvbSBpbnRlcnNlY3Rpb24gUyB0byBpbnRlcnNlY3Rpb24gRSB0aGF0IHRyYXZlcnNlcyBleGFjdGx5IE4gY293IHRyYWlscy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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