시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 2423 251 174 23.836%

문제

준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈이 많은 준영이는 고민 끝에 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+XHJcblxyXG48cD5cdWJiMzhcdWM4MWNcdWIyOTQgTlx1YWMxY1x1Yzc1OCBcdWIzYzRcdWMyZGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwIFx1YWRmOCBcdWMwYWNcdWM3NzQgXHViM2M0XHViODVjXHViNGU0XHVhY2ZjIFx1Yzc3NCBcdWIzYzRcdWI4NWNcdWI5N2MgXHVkMWI1XHVhY2ZjXHVkNTYwIFx1YjU0YyBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMgXHVjZDVjXHVjMThjIFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWFjNzhcdWI5YWNcdWIzYzRcdWI4NWQgXHVkNTU4XHViMjk0IEtcdWFjMWNcdWM3NTggXHVjNzc0XHVkNTU4XHVjNzU4IFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWQzZWNcdWM3YTVcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMgXHViM2M0XHViODVjXHViOTdjIFx1ZDNlY1x1YzdhNVx1ZDU1OFx1YWM4YyBcdWI0MThcdWJhNzQgXHViM2M0XHViODVjXHViOTdjIFx1YzljMFx1YjA5OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzc0IDBcdWM3NzRcdWI3N2MgXHVkNTU4XHVjNzkwLiBcdWI2MTBcdWQ1NWMgXHVkM2I4XHVjNzU4XHVjMGMxIFx1YzExY1x1YzZiOFx1Yzc0MCAxXHViYzg4IFx1YjNjNFx1YzJkYywgXHVkM2VjXHVjYzljXHVjNzQwIE5cdWJjODggXHViM2M0XHVjMmRjXHViNzdjIFx1ZDU1OFx1YWNlMCAxXHViYzg4XHVjNWQwXHVjMTFjIE5cdWJjODhcdWFlNGNcdWM5YzAgXHVkNTZkXHVjMGMxIFx1YWMwOCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YjljYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWMyMTggTigxICZsZTsgTiAmbGU7IDEwLDAwMClcdWFjZmMgXHViM2M0XHViODVjXHVjNzU4IFx1YzIxOCBNKDEgJmxlOyBNICZsZTsgNTAsMDAwKVx1YWNmYyBcdWQzZWNcdWM3YTVcdWQ1NjAgXHViM2M0XHViODVjXHVjNzU4IFx1YzIxOCBLKDEgJmxlOyBLICZsZTsgMjApXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBNXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHViM2M0XHViODVjXHViOTdjIFx1YzVmMFx1YWNiMFx1YzlkM1x1YjI5NCBcdWI0NTAgXHViM2M0XHVjMmRjXHVjNjQwIFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWQxYjVcdWFjZmNcdWQ1NThcdWIyOTRcdWIzNzAgXHVhYzc4XHViOWFjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjNjNFx1Yjg1Y1x1YjRlNFx1Yzc0MCBcdWM1OTFcdWJjMjlcdWQ1YTUgXHViM2M0XHViODVjXHVjNzc0XHViYTcwLCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzQwIDEsMDAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIEtcdWFjMWMgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YjNjNFx1Yjg1Y1x1Yjk3YyBcdWQzZWNcdWM3YTVcdWQ1NThcdWM1ZWMgXHVjNWJiXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZDVjXHVjMThjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMTE2MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJldmFtcGluZyBUcmFpbHMiLCJkZXNjcmlwdGlvbiI6IjxwPkZhcm1lciBKb2huIGR1dGlmdWxseSBjaGVja3Mgb24gdGhlIGNvd3MgZXZlcnkgZGF5LiBIZSB0cmF2ZXJzZXMgc29tZSBvZiB0aGUgTSAoMSAmbHQ7PSBNICZsdDs9IDUwLDAwMCkgdHJhaWxzIGNvbnZlbmllbnRseSBudW1iZXJlZCAxLi5NIGZyb20gcGFzdHVyZSAxIGFsbCB0aGUgd2F5IG91dCB0byBwYXN0dXJlIE4gKGEgam91cm5leSB3aGljaCBpcyBhbHdheXMgcG9zc2libGUgZm9yIHRyYWlsIG1hcHMgZ2l2ZW4gaW4gdGhlIHRlc3QgZGF0YSkuIFRoZSBOICgxICZsdDs9IE4gJmx0Oz0gMTAsMDAwKSBwYXN0dXJlcyBjb252ZW5pZW50bHkgbnVtYmVyZWQgMS4uTiBvbiBGYXJtZXIgSm9obiYjMzk7cyBmYXJtIGFyZSBjdXJyZW50bHkgY29ubmVjdGVkIGJ5IGJpZGlyZWN0aW9uYWwgZGlydCB0cmFpbHMuICZuYnNwO0VhY2ggdHJhaWwgaSBjb25uZWN0cyBwYXN0dXJlcyBQMV9pIGFuZCBQMl9pICgxICZsdDs9IFAxX2kgJmx0Oz0gTjsgMSAmbHQ7PSBQMl9pICZsdDs9IE4pIGFuZCByZXF1aXJlcyBUX2kgKDEgJmx0Oz0gVF9pICZsdDs9IDEsMDAwLDAwMCkgdW5pdHMgb2YgdGltZSB0byB0cmF2ZXJzZS48XC9wPlxyXG5cclxuPHA+SGUgd2FudHMgdG8gcmV2YW1wIHNvbWUgb2YgdGhlIHRyYWlscyBvbiBoaXMgZmFybSB0byBzYXZlIHRpbWUgb24gaGlzIGxvbmcgam91cm5leS4gU3BlY2lmaWNhbGx5LCBoZSB3aWxsIGNob29zZSBLICgxICZsdDs9IEsgJmx0Oz0gMjApIHRyYWlscyB0byB0dXJuIGludG8gaGlnaHdheXMsIHdoaWNoIHdpbGwgZWZmZWN0aXZlbHkgcmVkdWNlIHRoZSB0cmFpbCYjMzk7cyB0cmF2ZXJzYWwgdGltZSB0byAwLiBIZWxwIEZKIGRlY2lkZSB3aGljaCB0cmFpbHMgdG8gcmV2YW1wIHRvIG1pbmltaXplIHRoZSByZXN1bHRpbmcgdGltZSBvZiBnZXR0aW5nIGZyb20gcGFzdHVyZSAxIHRvIE4uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD4qIExpbmUgMTogVGhyZWUgc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOiBOLCBNLCBhbmQgSzxcL3A+XHJcblxyXG48cD4qIExpbmVzIDIuLk0rMTogTGluZSBpKzEgZGVzY3JpYmVzIHRyYWlsIGkgd2l0aCB0aHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IFAxX2ksIFAyX2ksIGFuZCBUX2k8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4qIExpbmUgMTogVGhlIGxlbmd0aCBvZiB0aGUgc2hvcnRlc3QgcGF0aCBhZnRlciByZXZhbXBpbmcgbm8gbW9yZSB0aGFuIEsgZWRnZXM8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

  • 문제를 번역한 사람: author6
  • 데이터를 추가한 사람: djm03178
  • 빠진 조건을 찾은 사람: kdk8361