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

문제

준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈이 많은 준영이는 고민 끝에 K개의 도로를 포장하여 서울에서 포천까지 가는 시간을 단축하려 한다.

문제는 N개의 도시가 주어지고 그 사이 도로와 이 도로를 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장하는 것이다. 도로는 이미 있는 도로만 포장할 수 있고, 포장하게 되면 도로를 지나는데 걸리는 시간이 0이 된다. 또한 편의상 서울은 1번 도시, 포천은 N번 도시라 하고 1번에서 N번까지 항상 갈 수 있는 데이터만 주어진다.

입력

첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하는데 걸리는 시간이 주어진다. 도로들은 양방향 도로이며, 걸리는 시간은 1,000,000보다 작거나 같은 자연수이다.

출력

첫 줄에 K개 이하의 도로를 포장하여 얻을 수 있는 최소 시간을 출력한다.

예제 입력 1

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

예제 출력 1

1
W3sicHJvYmxlbV9pZCI6IjExNjIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIzYzRcdWI4NWNcdWQzZWNcdWM3YTUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzkwMFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWI5ZTRcdWM3N2MgXHVjMTFjXHVjNmI4XHVjNWQwXHVjMTFjIFx1ZDNlY1x1Y2M5Y1x1YWU0Y1x1YzljMCBcdWNkOWNcdWQxZjRcdWFkZmNcdWM3NDQgXHVkNTVjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHVjN2EwXHVjNzc0IFx1YjljZVx1Yzc0MCBcdWM5MDBcdWM2MDFcdWM3NzRcdWIyOTQgXHViMmE2XHVjN2EwXHVjNzQ0IFx1Yzc5MCBcdWQzZWNcdWNjOWNcdWM1ZDAgXHViMmE2XHVhYzhjIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YWUzMCBcdWM3N2NcdWM0NjRcdWIyZTQuIFx1YjNjOFx1Yzc3NCBcdWI5Y2VcdWM3NDAgXHVjOTAwXHVjNjAxXHVjNzc0XHViMjk0IFx1YWNlMFx1YmJmYyBcdWIwNWRcdWM1ZDAgS1x1YWMxY1x1Yzc1OCBcdWIzYzRcdWI4NWNcdWI5N2MgXHVkM2VjXHVjN2E1XHVkNTU4XHVjNWVjIFx1YzExY1x1YzZiOFx1YzVkMFx1YzExYyBcdWQzZWNcdWNjOWNcdWFlNGNcdWM5YzAgXHVhYzAwXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWIyZThcdWNkOTVcdWQ1NThcdWI4MjQgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJiMzhcdWM4MWNcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWIzYzRcdWMyZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwIFx1YWRmOCBcdWMwYWNcdWM3NzQgXHViM2M0XHViODVjXHVjNjQwJm5ic3A7XHVjNzc0IFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWQxYjVcdWFjZmNcdWQ1NjAgXHViNTRjIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YyBcdWNkNWNcdWMxOGMgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YWM3OFx1YjlhY1x1YjNjNFx1Yjg1ZCBcdWQ1NThcdWIyOTQgS1x1YWMxY1x1Yzc1OCBcdWM3NzRcdWQ1NThcdWM3NTggXHViM2M0XHViODVjXHViOTdjIFx1ZDNlY1x1YzdhNVx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuJm5ic3A7XHViM2M0XHViODVjXHViMjk0IFx1Yzc3NFx1YmJmOCBcdWM3ODhcdWIyOTQgXHViM2M0XHViODVjXHViOWNjIFx1ZDNlY1x1YzdhNVx1ZDU2MCBcdWMyMTggXHVjNzg4XHVhY2UwLCZuYnNwO1x1ZDNlY1x1YzdhNVx1ZDU1OFx1YWM4YyBcdWI0MThcdWJhNzQgXHViM2M0XHViODVjXHViOTdjIFx1YzljMFx1YjA5OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0IDBcdWM3NzQgXHViNDFjXHViMmU0LiBcdWI2MTBcdWQ1NWMgXHVkM2I4XHVjNzU4XHVjMGMxIFx1YzExY1x1YzZiOFx1Yzc0MCAxXHViYzg4IFx1YjNjNFx1YzJkYywgXHVkM2VjXHVjYzljXHVjNzQwIE5cdWJjODggXHViM2M0XHVjMmRjXHViNzdjIFx1ZDU1OFx1YWNlMCAxXHViYzg4XHVjNWQwXHVjMTFjIE5cdWJjODhcdWFlNGNcdWM5YzAgXHVkNTZkXHVjMGMxIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YjljYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWMyMTggTigxICZsZTsgTiAmbGU7IDEwLDAwMClcdWFjZmMgXHViM2M0XHViODVjXHVjNzU4IFx1YzIxOCBNKDEgJmxlOyBNICZsZTsgNTAsMDAwKVx1YWNmYyBcdWQzZWNcdWM3YTVcdWQ1NjAgXHViM2M0XHViODVjXHVjNzU4IFx1YzIxOCBLKDEgJmxlOyBLICZsZTsgMjApXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHViM2M0XHViODVjXHVhYzAwIFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NCZuYnNwO1x1YjQ1MCBcdWIzYzRcdWMyZGNcdWM2NDAgXHViM2M0XHViODVjXHViOTdjIFx1ZDFiNVx1YWNmY1x1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViM2M0XHViODVjXHViNGU0XHVjNzQwIFx1YzU5MVx1YmMyOVx1ZDVhNSBcdWIzYzRcdWI4NWNcdWM3NzRcdWJhNzAsIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDAgMSwwMDAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgS1x1YWMxYyBcdWM3NzRcdWQ1NThcdWM3NTggXHViM2M0XHViODVjXHViOTdjIFx1ZDNlY1x1YzdhNVx1ZDU1OFx1YzVlYyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWMxOGMgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIxMTYyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUmV2YW1waW5nIFRyYWlscyIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvaG4gZHV0aWZ1bGx5IGNoZWNrcyBvbiB0aGUgY293cyBldmVyeSBkYXkuIEhlIHRyYXZlcnNlcyBzb21lIG9mIHRoZSBNICgxICZsdDs9IE0gJmx0Oz0gNTAsMDAwKSB0cmFpbHMgY29udmVuaWVudGx5IG51bWJlcmVkIDEuLk0gZnJvbSBwYXN0dXJlIDEgYWxsIHRoZSB3YXkgb3V0IHRvIHBhc3R1cmUgTiAoYSBqb3VybmV5IHdoaWNoIGlzIGFsd2F5cyBwb3NzaWJsZSBmb3IgdHJhaWwgbWFwcyBnaXZlbiBpbiB0aGUgdGVzdCBkYXRhKS4gVGhlIE4gKDEgJmx0Oz0gTiAmbHQ7PSAxMCwwMDApIHBhc3R1cmVzIGNvbnZlbmllbnRseSBudW1iZXJlZCAxLi5OIG9uIEZhcm1lciBKb2huJiMzOTtzIGZhcm0gYXJlIGN1cnJlbnRseSBjb25uZWN0ZWQgYnkgYmlkaXJlY3Rpb25hbCBkaXJ0IHRyYWlscy4gJm5ic3A7RWFjaCB0cmFpbCBpIGNvbm5lY3RzIHBhc3R1cmVzIFAxX2kgYW5kIFAyX2kgKDEgJmx0Oz0gUDFfaSAmbHQ7PSBOOyAxICZsdDs9IFAyX2kgJmx0Oz0gTikgYW5kIHJlcXVpcmVzIFRfaSAoMSAmbHQ7PSBUX2kgJmx0Oz0gMSwwMDAsMDAwKSB1bml0cyBvZiB0aW1lIHRvIHRyYXZlcnNlLjxcL3A+XHJcblxyXG48cD5IZSB3YW50cyB0byByZXZhbXAgc29tZSBvZiB0aGUgdHJhaWxzIG9uIGhpcyBmYXJtIHRvIHNhdmUgdGltZSBvbiBoaXMgbG9uZyBqb3VybmV5LiBTcGVjaWZpY2FsbHksIGhlIHdpbGwgY2hvb3NlIEsgKDEgJmx0Oz0gSyAmbHQ7PSAyMCkgdHJhaWxzIHRvIHR1cm4gaW50byBoaWdod2F5cywgd2hpY2ggd2lsbCBlZmZlY3RpdmVseSByZWR1Y2UgdGhlIHRyYWlsJiMzOTtzIHRyYXZlcnNhbCB0aW1lIHRvIDAuIEhlbHAgRkogZGVjaWRlIHdoaWNoIHRyYWlscyB0byByZXZhbXAgdG8gbWluaW1pemUgdGhlIHJlc3VsdGluZyB0aW1lIG9mIGdldHRpbmcgZnJvbSBwYXN0dXJlIDEgdG8gTi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPiogTGluZSAxOiBUaHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IE4sIE0sIGFuZCBLPFwvcD5cclxuXHJcbjxwPiogTGluZXMgMi4uTSsxOiBMaW5lIGkrMSBkZXNjcmliZXMgdHJhaWwgaSB3aXRoIHRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogUDFfaSwgUDJfaSwgYW5kIFRfaTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPiogTGluZSAxOiBUaGUgbGVuZ3RoIG9mIHRoZSBzaG9ydGVzdCBwYXRoIGFmdGVyIHJldmFtcGluZyBubyBtb3JlIHRoYW4gSyBlZGdlczxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > USA Computing Olympiad > 2008-2009 Season > USACO February 2009 Contest > Gold 3번