시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 455 203 162 48.214%

문제

TSP는 매우 유명한 문제이다. 이 문제는 NP-hard 문제이기 때문에 효율적인 해법이 존재하지 않는다. 이번에는 약간 변형된 TSP 문제를 풀어보자.

TSP문제는 도시 N개를 모두 한 번씩 방문하는 문제이다. 도시는 1번부터 N번까지 번호가 붙여져 있다. 각 도시 사이의 거리는 모두 알려져 있으며, 모든 도시를 방문하는데 드는 시간을 최소로 해야 한다.

번호가 K인 도시를 방문하려면, K보다 작은 번호를 가진 모든 도시를 K번을 방문하기 전에 모두 방문하거나, 방문한 후에 모두 방문해야 한다. 즉, K보다 번호가 작은 도시 중 하나를 K번 이전에 방문하고, 다른 하나를 K번 이후에 방문하면 안된다.

위의 조건을 만족하면서 모든 도시를 방문하는데 드는 시간의 최소값을 구하는 프로그램을 작성하시오. 첫 도시와 마지막 도시는 같지 않아도 되며, 어느 도시에서 시작하고 마쳐도 상관없다.

입력

첫째 줄에 도시의 수 N (2 ≤ N ≤ 1500)이 주어진다.

다음 N개 줄에는 [0, 1000] 구간에 포함되는 양의 정수가 주어진다. A번째 행의 B번째 숫자는 A에서 B로 가는데 필요한 시간이고, 이 수는 B번 행의 A번째 숫자와 같다. A와 B가 같은 경우에는 0이 주어지며, 이외의 경우에는 항상 양의 정수이다.

출력

첫째 줄에 문제의 조건을 만족하면서 모든 도시를 방문하는데 드는 시간의 최소값을 출력한다.

예제 입력 1

3
0 5 2
5 0 4
2 4 0

예제 출력 1

7

힌트

가능한 방문 순서는 2, 1, 3과 3, 1, 2가 있다. 1, 3, 2가 시간이 더 적게 들지만, 문제의 조건을 만족하지 않는다.

W3sicHJvYmxlbV9pZCI6Ijk1MjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJOUC1oYXJkIiwiZGVzY3JpcHRpb24iOiI8cD5UU1BcdWIyOTQgXHViOWU0XHVjNmIwIFx1YzcyMFx1YmE4NVx1ZDU1YyBcdWJiMzhcdWM4MWNcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWIyOTQgTlAtaGFyZCBcdWJiMzhcdWM4MWNcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1ZDZhOFx1YzcyOFx1YzgwMVx1Yzc3OCBcdWQ1NzRcdWJjOTVcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjNzc0XHViYzg4XHVjNWQwXHViMjk0IFx1YzU3ZFx1YWMwNCBcdWJjYzBcdWQ2MTVcdWI0MWMgVFNQIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWQ0ODBcdWM1YjRcdWJjZjRcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlRTUFx1YmIzOFx1YzgxY1x1YjI5NCBcdWIzYzRcdWMyZGMgTlx1YWMxY1x1Yjk3YyBcdWJhYThcdWI0NTAgXHVkNTVjIFx1YmM4OFx1YzUyOSBcdWJjMjlcdWJiMzhcdWQ1NThcdWIyOTQgXHViYjM4XHVjODFjXHVjNzc0XHViMmU0LiBcdWIzYzRcdWMyZGNcdWIyOTQgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWM1ZWNcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHViM2M0XHVjMmRjIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWIyOTQgXHViYWE4XHViNDUwIFx1YzU0Y1x1YjgyNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YmFhOFx1YjRlMCBcdWIzYzRcdWMyZGNcdWI5N2MgXHViYzI5XHViYjM4XHVkNTU4XHViMjk0XHViMzcwIFx1YjRkY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmM4OFx1ZDYzOFx1YWMwMCBLXHVjNzc4IFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWJjMjlcdWJiMzhcdWQ1NThcdWI4MjRcdWJhNzQsIEtcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWFjMDBcdWM5YzQgXHViYWE4XHViNGUwIFx1YjNjNFx1YzJkY1x1Yjk3YyBLXHViYzg4XHVjNzQ0IFx1YmMyOVx1YmIzOFx1ZDU1OFx1YWUzMCBcdWM4MDRcdWM1ZDAgXHViYWE4XHViNDUwIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YWM3MFx1YjA5OCwgXHViYzI5XHViYjM4XHVkNTVjIFx1ZDZjNFx1YzVkMCBcdWJhYThcdWI0NTAgXHViYzI5XHViYjM4XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBLXHViY2Y0XHViMmU0IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM3OTFcdWM3NDAgXHViM2M0XHVjMmRjIFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgS1x1YmM4OCBcdWM3NzRcdWM4MDRcdWM1ZDAgXHViYzI5XHViYjM4XHVkNTU4XHVhY2UwLCBcdWIyZTRcdWI5NzggXHVkNTU4XHViMDk4XHViOTdjIEtcdWJjODggXHVjNzc0XHVkNmM0XHVjNWQwIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHViYTc0XHVjMTFjIFx1YmFhOFx1YjRlMCBcdWIzYzRcdWMyZGNcdWI5N2MgXHViYzI5XHViYjM4XHVkNTU4XHViMjk0XHViMzcwIFx1YjRkY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWNjYWIgXHViM2M0XHVjMmRjXHVjNjQwIFx1YjljOFx1YzljMFx1YjljOSBcdWIzYzRcdWMyZGNcdWIyOTQgXHVhYzE5XHVjOWMwIFx1YzU0YVx1YzU0NFx1YjNjNCBcdWI0MThcdWJhNzAsIFx1YzViNFx1YjI5MCBcdWIzYzRcdWMyZGNcdWM1ZDBcdWMxMWMgXHVjMmRjXHVjNzkxXHVkNTU4XHVhY2UwIFx1YjljOFx1Y2NkMFx1YjNjNCBcdWMwYzFcdWFkMDBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWMyMTggTiAoMiAmbGU7IE4gJmxlOyAxNTAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBbMCwgMTAwMF0gXHVhZDZjXHVhYzA0XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YjI5NCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gQVx1YmM4OFx1YzlmOCBcdWQ1ODlcdWM3NTggQlx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWIyOTQgQVx1YzVkMFx1YzExYyBCXHViODVjIFx1YWMwMFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjMmRjXHVhYzA0XHVjNzc0XHVhY2UwLCBcdWM3NzQgXHVjMjE4XHViMjk0IEJcdWJjODggXHVkNTg5XHVjNzU4IEFcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHVjNjQwIFx1YWMxOVx1YjJlNC4gQVx1YzY0MCBCXHVhYzAwIFx1YWMxOVx1Yzc0MCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1Yzc3NFx1YzY3OFx1Yzc1OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVkNTZkXHVjMGMxIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YmE3NFx1YzExYyBcdWJhYThcdWI0ZTAgXHViM2M0XHVjMmRjXHViOTdjIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWI0ZGNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzU4IFx1Y2Q1Y1x1YzE4Y1x1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YWMwMFx1YjJhNVx1ZDU1YyBcdWJjMjlcdWJiMzggXHVjMjFjXHVjMTFjXHViMjk0IDIsIDEsIDNcdWFjZmMgMywgMSwgMlx1YWMwMCBcdWM3ODhcdWIyZTQuIDEsIDMsIDJcdWFjMDAgXHVjMmRjXHVhYzA0XHVjNzc0IFx1YjM1NCBcdWM4MDFcdWFjOGMgXHViNGU0XHVjOWMwXHViOWNjLCBcdWJiMzhcdWM4MWNcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5NTIwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUFVUTklLIiwiZGVzY3JpcHRpb24iOiI8cD5DaGFuY2VzIGFyZSB0aGF0IHlvdSBoYXZlIHByb2JhYmx5IGFscmVhZHkgaGVhcmQgb2YgdGhlIHRyYXZlbGxpbmcgc2FsZXNtYW4gcHJvYmxlbS4gSWYgeW91IGhhdmUsIHRoZW4geW91IGFyZSBhd2FyZSB0aGF0IGl0IGlzIGFuIE5QLWhhcmQgcHJvYmxlbSBiZWNhdXNlIGl0IGxhY2tzIGFuIGVmZmljaWVudCBzb2x1dGlvbi4gV2VsbCwgdGhpcyB0YXNrIGlzIGFuIHVuY29tbW9uIHZlcnNpb24gb2YgdGhlIGZhbW91cyBwcm9ibGVtISBJdHMgdW5jb21tb25uZXNzIGRlcml2ZXMgZnJvbSB0aGUgZmFjdCB0aGF0IHRoaXMgdmVyc2lvbiBpcywgYWN0dWFsbHksIHNvbHZhYmxlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdHJhdmVsbGluZyBzYWxlc21hbiBpcyBvbiBhIG1pc3Npb24gdG8gdmlzaXQgTiBjaXRpZXMsIGVhY2ggZXhhY3RseSBvbmNlLiBUaGUgY2l0aWVzIGFyZSByZXByZXNlbnRlZCBieSBudW1iZXJzIDEsIDIsIC4uLiwgTi4gV2hhdCB3ZSBrbm93IGlzIHRoZSBkaXJlY3QgZmxpZ2h0IGR1cmF0aW9uIGJldHdlZW4gZWFjaCBwYWlyIG9mIGNpdGllcy4gVGhlIHNhbGVzbWFuLCBiZWluZyB0aGUgZWZmaWNpZW50IG1hbiB0aGF0IGhlIGlzLCB3YW50cyB0byBtb2RpZnkgdGhlIGNpdHkgdmlzaXRpbmcgc2VxdWVuY2Ugc28gdGhhdCB0aGUgdG90YWwgZmxpZ2h0IGR1cmF0aW9uIGlzIHRoZSBtaW5pbXVtIHBvc3NpYmxlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BbGFzLCBhbGwgaXMgbm90IHNvIHNpbXBsZS4gSW4gYWRkaXRpb24sIHRoZSBzYWxlc21hbiBoYXMgYSBwZWN1bGlhciBjb25kaXRpb24gcmVnYXJkaW5nIHRoZSBzZXF1ZW5jZS4gRm9yIGVhY2ggY2l0eSBsYWJlbGVkIEsgbXVzdCBhcHBseTogZWl0aGVyIGFsbCBjaXRpZXMgd2l0aCBsYWJlbHMgc21hbGxlciB0aGFuIEsgaGF2ZSBiZWVuIHZpc2l0ZWQgYmVmb3JlIHRoZSBjaXR5IGxhYmVsZWQgSyBvciB0aGV5IHdpbGwgYWxsIGJlIHZpc2l0ZWQgYWZ0ZXIgdGhlIGNpdHkgbGFiZWxlZCBLLiBJbiBvdGhlciB3b3JkcywgdGhlIHNpdHVhdGlvbiB3aGVuIG9uZSBvZiBzdWNoIGNpdGllcyBpcyB2aXNpdGVkIGJlZm9yZSwgYW5kIHRoZSBvdGhlciBhZnRlciBpcyBub3QgYWxsb3dlZC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QXNzaXN0IHRoZSBwb29yIGZlbGxvdyBpbiBoaXMgYW1iaXRpb3VzIG1pc3Npb24gYW5kIGNhbGN1bGF0ZSB0aGUgbWluaW11bSB0b3RhbCBmbGlnaHQgZHVyYXRpb24gbmVlZGVkIGluIG9yZGVyIHRvIHRyYXZlbCB0byBhbGwgdGhlIGNpdGllcywgc3RhcnRpbmcgZnJvbSB3aGljaGV2ZXIgYW5kIGVuZGluZyBpbiB3aGljaGV2ZXIgY2l0eSwgdmlzaXRpbmcgZXZlcnkgY2l0eSBleGFjdGx5IG9uY2UsIHNvIHRoYXQgaGlzIHBlY3VsaWFyIHJlcXVlc3QgaXMgZnVsZmlsbGVkLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIHBvc2l0aXZlIGludGVnZXIgTiAoMiAmbGU7IE4gJmxlOyAxNTAwKSwgdGhlIG51bWJlciBvZiBjaXRpZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIE4gcG9zaXRpdmUgaW50ZWdlcnMgZnJvbSB0aGUgaW50ZXJ2YWwgWzAsIDEwMDBdLiBUaGUgbnVtYmVyIGluIEI8c3VwPnRoPFwvc3VwPiBwbGFjZSBpbiB0aGUgQTxzdXA+dGg8XC9zdXA+IHJvdyByZXByZXNlbnRzIHRoZSBmbGlnaHQgZHVyYXRpb24gYmV0d2VlbiBjaXRpZXMgQSBhbmQgQjsgdGhhdCBudW1iZXIgaXMgZXF1YWwgdG8gdGhlIEE8c3VwPnRoPFwvc3VwPiBudW1iZXIgaW4gdGhlIEI8c3VwPnRoPFwvc3VwPiByb3cuIFdoZW4gQSA9IEIsIHRoYXQgbnVtYmVyIGlzIDAuIE90aGVyd2lzZSwgaXQgaXMgYSBwb3NpdGl2ZSB2YWx1ZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSByZXF1aXJlZCBtaW5pbXVtIHRvdGFsIGZsaWdodCBkdXJhdGlvbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBvcHRpbWFsIHNlcXVlbmNlIGlzIDIsIDEsIDMgb3IgMywgMSwgMi4gVGhlIHNlcXVlbmNlIDEsIDMsIDIgaXMgZXZlbiBtb3JlIGZhdm91cmFibGUsIGJ1dCBpdCBkb2VzIG5vdCBmdWxmaWxsIHRoZSBzYWxlc21hbiYjMzk7cyBjb25kaXRpb24uJm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d