시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 13868 6340 4140 43.930%

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

예제 입력 1

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

예제 출력 1

10
W3sicHJvYmxlbV9pZCI6IjEyMzgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQzMGNcdWQyZjAiLCJkZXNjcmlwdGlvbiI6IjxwPk5cdWFjMWNcdWM3NTggXHVjMjJiXHVjNzkwXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxYyBcdWFjMDFcdWFjMDFcdWM3NTggXHViOWM4XHVjNzQ0XHVjNWQwIFx1ZDU1YyBcdWJhODVcdWM3NTggXHVkNTU5XHVjMGRkXHVjNzc0IFx1YzBiNFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1YjI5MCBcdWIwYTAgXHVjNzc0IE5cdWJhODVcdWM3NTggXHVkNTU5XHVjMGRkXHVjNzc0IFggKDEgJmxlOyZuYnNwO1ggJmxlOyBOKVx1YmM4OCBcdWI5YzhcdWM3NDRcdWM1ZDAgXHViYWE4XHVjNWVjXHVjMTFjIFx1ZDMwY1x1ZDJmMFx1Yjk3YyBcdWJjOGNcdWM3NzRcdWFlMzBcdWI4NWMgXHVkNTg4XHViMmU0LiBcdWM3NzQgXHViOWM4XHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMFx1YjI5NCBcdWNkMWQgTVx1YWMxY1x1Yzc1OCBcdWIyZThcdWJjMjlcdWQ1YTUgXHViM2M0XHViODVjXHViNGU0XHVjNzc0IFx1Yzc4OFx1YWNlMCBpXHViYzg4XHVjOWY4IFx1YWUzOFx1Yzc0NCBcdWM5YzBcdWIwOThcdWIyOTRcdWIzNzAgVDxzdWI+aTxcL3N1Yj4oMSAmbGU7IFQ8c3ViPmk8XC9zdWI+ICZsZTsgMTAwKVx1Yzc1OCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjMThjXHViZTQ0XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQwIFx1ZDMwY1x1ZDJmMFx1YzVkMCBcdWNjMzhcdWMxMWRcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YWM3OFx1YzViNFx1YWMwMFx1YzExYyBcdWIyZTRcdWMyZGMgXHVhZGY4XHViNGU0XHVjNzU4IFx1YjljOFx1Yzc0NFx1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2NDBcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHVjNzc0IFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWM2Y2NcdWIwOTkgXHVhYzhjXHVjNzQ0XHViN2VjXHVjMTFjIFx1Y2Q1Y1x1YjJlOCBcdWMyZGNcdWFjMDRcdWM1ZDAgXHVjNjI0XHVhY2UwIFx1YWMwMFx1YWUzMFx1Yjk3YyBcdWM2ZDBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWIzYzRcdWI4NWNcdWI0ZTRcdWM3NDAgXHViMmU4XHViYzI5XHVkNWE1XHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM1NDRcdWI5YzggXHVhZGY4XHViNGU0XHVjNzc0IFx1YzYyNFx1YWNlMCBcdWFjMDBcdWIyOTQgXHVhZTM4XHVjNzc0IFx1YjJlNFx1Yjk3Y1x1YzljMFx1YjNjNCBcdWJhYThcdWI5NzhcdWIyZTQuIE5cdWJhODVcdWM3NTggXHVkNTU5XHVjMGRkXHViNGU0IFx1YzkxMSBcdWM2MjRcdWFjZTAgXHVhYzAwXHViMjk0XHViMzcwIFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NDAgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YzE4Y1x1YmU0NFx1ZDU1OFx1YjI5NCBcdWQ1NTlcdWMwZGRcdWM3NDAgXHViMjA0XHVhZDZjXHVjNzdjXHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YzVlY1x1Yjc3Yy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTigxICZsZTsmbmJzcDtOICZsZTsgMSwwMDApLCBNKDEgJmxlOyBNICZsZTsgMTAsMDAwKSwgWFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1Yzc4NVx1YjgyNVx1YjQxY1x1YjJlNC4gXHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTSsxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMCBpXHViYzg4XHVjOWY4IFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWMyZGNcdWM3OTFcdWM4MTAsIFx1YjA1ZFx1YzgxMCwgXHVhZGY4XHViOWFjXHVhY2UwIFx1Yzc3NCBcdWIzYzRcdWI4NWNcdWI5N2MgXHVjOWMwXHViMDk4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWMxOGNcdWM2OTRcdWMyZGNcdWFjMDQgVDxzdWI+aTxcL3N1Yj5cdWFjMDAgXHViNGU0XHVjNWI0XHVjNjI4XHViMmU0LiBcdWMyZGNcdWM3OTFcdWM4MTBcdWFjZmMgXHViMDVkXHVjODEwXHVjNzc0IFx1YWMxOVx1Yzc0MCBcdWIzYzRcdWI4NWNcdWIyOTQgXHVjNWM2XHVjNzNjXHViYTcwLCBcdWMyZGNcdWM3OTFcdWM4MTBcdWFjZmMgXHVkNTVjIFx1YjNjNFx1YzJkYyBBXHVjNWQwXHVjMTFjIFx1YjJlNFx1Yjk3OCBcdWIzYzRcdWMyZGMgQlx1Yjg1YyBcdWFjMDBcdWIyOTQgXHViM2M0XHViODVjXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWNkNWNcdWIzMDAgMVx1YWMxY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc0MCBcdWM5ZDFcdWM1ZDBcdWMxMWMgWFx1YzVkMCBcdWFjMDhcdWMyMTggXHVjNzg4XHVhY2UwLCBYXHVjNWQwXHVjMTFjIFx1YzlkMVx1YzczY1x1Yjg1YyBcdWIzY2NcdWM1NDRcdWM2MmMgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWIzNzBcdWM3NzRcdWQxMzBcdWI5Y2MgXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBOXHViYTg1XHVjNzU4IFx1ZDU1OVx1YzBkZFx1YjRlNCBcdWM5MTEgXHVjNjI0XHVhY2UwIFx1YWMwMFx1YjI5NFx1YjM3MCBcdWFjMDBcdWM3YTUgXHVjNjI0XHViNzk4IFx1YWM3OFx1YjlhY1x1YjI5NCBcdWQ1NTlcdWMwZGRcdWM3NTggXHVjMThjXHVjNjk0XHVjMmRjXHVhYzA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMjM4IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU2lsdmVyIENvdyBQYXJ0eSIsImRlc2NyaXB0aW9uIjoiPHA+T25lIGNvdyBmcm9tIGVhY2ggb2YgTiBmYXJtcyAoMSAmbHQ7PSBOICZsdDs9IDEwMDApIGNvbnZlbmllbnRseSBudW1iZXJlZCAxLi5OIGlzIGdvaW5nIHRvIGF0dGVuZCB0aGUgYmlnIGNvdyBwYXJ0eSB0byBiZSBoZWxkIGF0IGZhcm0gI1ggKDEgJmx0Oz0gWCAmbHQ7PSBOKS4gQSB0b3RhbCBvZiBNICgxICZsdDs9IE0gJmx0Oz0gMTAwLDAwMCkgdW5pZGlyZWN0aW9uYWwgKG9uZS13YXkpIHJvYWRzIGNvbm5lY3RzIHBhaXJzIG9mIGZhcm1zOyByb2FkIGkgcmVxdWlyZXMgVGkgKDEgJmx0Oz0gVGkgJmx0Oz0gMTAwKSB1bml0cyBvZiB0aW1lIHRvIHRyYXZlcnNlLjxcL3A+XHJcblxyXG48cD5FYWNoIGNvdyBtdXN0IHdhbGsgdG8gdGhlIHBhcnR5IGFuZCwgd2hlbiB0aGUgcGFydHkgaXMgb3ZlciwgcmV0dXJuIHRvIGhlciBmYXJtLiBFYWNoIGNvdyBpcyBsYXp5IGFuZCB0aHVzIHBpY2tzIGFuIG9wdGltYWwgcm91dGUgd2l0aCB0aGUgc2hvcnRlc3QgdGltZS4gQSBjb3cmIzM5O3MgcmV0dXJuIHJvdXRlIG1pZ2h0IGJlIGRpZmZlcmVudCBmcm9tIGhlciBvcmlnaW5hbCByb3V0ZSB0byB0aGUgcGFydHkgc2luY2Ugcm9hZHMgYXJlIG9uZS13YXkuPFwvcD5cclxuXHJcbjxwPk9mIGFsbCB0aGUgY293cywgd2hhdCBpcyB0aGUgbG9uZ2VzdCBhbW91bnQgb2YgdGltZSBhIGNvdyBtdXN0IHNwZW5kIHdhbGtpbmcgdG8gdGhlIHBhcnR5IGFuZCBiYWNrPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+KiBMaW5lIDE6IFRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycywgcmVzcGVjdGl2ZWx5OiBOLCBNLCBhbmQgWDxcL3A+XHJcblxyXG48cD4qIExpbmVzIDIuLk0rMTogTGluZSBpKzEgZGVzY3JpYmVzIHJvYWQgaSB3aXRoIHRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogQWksIEJpLCBhbmQgVGkuIFRoZSBkZXNjcmliZWQgcm9hZCBydW5zIGZyb20gZmFybSBBaSB0byBmYXJtIEJpLCByZXF1aXJpbmcgVGkgdGltZSB1bml0cyB0byB0cmF2ZXJzZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4qIExpbmUgMTogT25lIGludGVnZXI6IHRoZSBtYXhpbXVtIG9mIHRpbWUgYW55IG9uZSBjb3cgbXVzdCB3YWxrLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > USA Computing Olympiad > 2006-2007 Season > USACO February 2007 Contest > Silver 3번

  • 문제를 번역한 사람: author6
  • 빠진 조건을 찾은 사람: his130