시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB85342233551.777%

문제

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

4
0 15 7 8
15 0 16 9
7 16 0 12
8 9 12 0

예제 출력 2

31

힌트

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

W3sicHJvYmxlbV9pZCI6Ijk1MjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJOUC1oYXJkIiwiZGVzY3JpcHRpb24iOiI8cD5UU1BcdWIyOTQgXHViOWU0XHVjNmIwIFx1YzcyMFx1YmE4NVx1ZDU1YyBcdWJiMzhcdWM4MWNcdWM3NzRcdWIyZTQuIFx1Yzc3NCBcdWJiMzhcdWM4MWNcdWIyOTQgTlAtaGFyZCBcdWJiMzhcdWM4MWNcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwIFx1ZDZhOFx1YzcyOFx1YzgwMVx1Yzc3OCBcdWQ1NzRcdWJjOTVcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVjNzc0XHViYzg4XHVjNWQwXHViMjk0IFx1YzU3ZFx1YWMwNCBcdWJjYzBcdWQ2MTVcdWI0MWMgVFNQIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWQ0ODBcdWM1YjRcdWJjZjRcdWM3OTAuPFwvcD5cclxuXHJcbjxwPlRTUFx1YmIzOFx1YzgxY1x1YjI5NCBcdWIzYzRcdWMyZGMgTlx1YWMxY1x1Yjk3YyBcdWJhYThcdWI0NTAgXHVkNTVjIFx1YmM4OFx1YzUyOSBcdWJjMjlcdWJiMzhcdWQ1NThcdWIyOTQgXHViYjM4XHVjODFjXHVjNzc0XHViMmU0LiBcdWIzYzRcdWMyZGNcdWIyOTQgMVx1YmM4OFx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWJkOTlcdWM1ZWNcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHViM2M0XHVjMmRjIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWIyOTQgXHViYWE4XHViNDUwIFx1YzU0Y1x1YjgyNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YmFhOFx1YjRlMCBcdWIzYzRcdWMyZGNcdWI5N2MgXHViYzI5XHViYjM4XHVkNTU4XHViMjk0XHViMzcwIFx1YjRkY1x1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDQgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmM4OFx1ZDYzOFx1YWMwMCBLXHVjNzc4IFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWJjMjlcdWJiMzhcdWQ1NThcdWI4MjRcdWJhNzQsIEtcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWFjMDBcdWM5YzQgXHViYWE4XHViNGUwIFx1YjNjNFx1YzJkY1x1Yjk3YyBLXHViYzg4XHVjNzQ0IFx1YmMyOVx1YmIzOFx1ZDU1OFx1YWUzMCBcdWM4MDRcdWM1ZDAgXHViYWE4XHViNDUwIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YWM3MFx1YjA5OCwgXHViYzI5XHViYjM4XHVkNTVjIFx1ZDZjNFx1YzVkMCBcdWJhYThcdWI0NTAgXHViYzI5XHViYjM4XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBLXHViY2Y0XHViMmU0IFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM3OTFcdWM3NDAgXHViM2M0XHVjMmRjIFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgS1x1YmM4OCBcdWM3NzRcdWM4MDRcdWM1ZDAgXHViYzI5XHViYjM4XHVkNTU4XHVhY2UwLCBcdWIyZTRcdWI5NzggXHVkNTU4XHViMDk4XHViOTdjIEtcdWJjODggXHVjNzc0XHVkNmM0XHVjNWQwIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3MDRcdWM3NTggXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YmE3NFx1YzExYyBcdWJhYThcdWI0ZTAgXHViM2M0XHVjMmRjXHViOTdjIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWI0ZGNcdWIyOTQgXHVjMmRjXHVhYzA0XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjY2FiIFx1YjNjNFx1YzJkY1x1YzY0MCBcdWI5YzhcdWM5YzBcdWI5YzkgXHViM2M0XHVjMmRjXHViMjk0IFx1YWMxOVx1YzljMCBcdWM1NGFcdWM1NDRcdWIzYzQgXHViNDE4XHViYTcwLCBcdWM1YjRcdWIyOTAgXHViM2M0XHVjMmRjXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YWNlMCBcdWI5YzhcdWNjZDBcdWIzYzQgXHVjMGMxXHVhZDAwXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzYzRcdWMyZGNcdWM3NTggXHVjMjE4IE4gKDIgJmxlOyBOICZsZTsgMTUwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgWzAsIDEwMDBdIFx1YWQ2Y1x1YWMwNFx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWIyOTQgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIEFcdWJjODhcdWM5ZjggXHVkNTg5XHVjNzU4IEJcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViMjk0IEFcdWM1ZDBcdWMxMWMgQlx1Yjg1YyBcdWFjMDBcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzJkY1x1YWMwNFx1Yzc3NFx1YWNlMCwgXHVjNzc0IFx1YzIxOFx1YjI5NCBCXHViYzg4IFx1ZDU4OVx1Yzc1OCBBXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YzY0MCBcdWFjMTlcdWIyZTQuIEFcdWM2NDAgQlx1YWMwMCBcdWFjMTlcdWM3NDAgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IDBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWM3NzRcdWM2NzhcdWM3NTggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYjM4XHVjODFjXHVjNzU4IFx1Yzg3MFx1YWM3NFx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWJhNzRcdWMxMWMgXHViYWE4XHViNGUwIFx1YjNjNFx1YzJkY1x1Yjk3YyBcdWJjMjlcdWJiMzhcdWQ1NThcdWIyOTRcdWIzNzAgXHViNGRjXHViMjk0IFx1YzJkY1x1YWMwNFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzYwOFx1YzgxY1x1Yzc1OCBcdWFjYmRcdWM2YjAgXHVhYzAwXHViMmE1XHVkNTVjIFx1YmMyOVx1YmIzOCBcdWMyMWNcdWMxMWNcdWIyOTQgMiwgMSwgM1x1YWNmYyAzLCAxLCAyXHVhYzAwIFx1Yzc4OFx1YjJlNC4gMSwgMywgMlx1YWMwMCBcdWMyZGNcdWFjMDRcdWM3NzQgXHViMzU0IFx1YzgwMVx1YWM4YyBcdWI0ZTRcdWM5YzBcdWI5Y2MsIFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWM4NzBcdWFjNzRcdWM3NDQgXHViOWNjXHVjODcxXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6Ijk1MjAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQVVROSUsiLCJkZXNjcmlwdGlvbiI6IjxwPkNoYW5jZXMgYXJlIHRoYXQgeW91IGhhdmUgcHJvYmFibHkgYWxyZWFkeSBoZWFyZCBvZiB0aGUgdHJhdmVsbGluZyBzYWxlc21hbiBwcm9ibGVtLiBJZiB5b3UgaGF2ZSwgdGhlbiB5b3UgYXJlIGF3YXJlIHRoYXQgaXQgaXMgYW4gTlAtaGFyZCBwcm9ibGVtIGJlY2F1c2UgaXQgbGFja3MgYW4gZWZmaWNpZW50IHNvbHV0aW9uLiBXZWxsLCB0aGlzIHRhc2sgaXMgYW4gdW5jb21tb24gdmVyc2lvbiBvZiB0aGUgZmFtb3VzIHByb2JsZW0hIEl0cyB1bmNvbW1vbm5lc3MgZGVyaXZlcyBmcm9tIHRoZSBmYWN0IHRoYXQgdGhpcyB2ZXJzaW9uIGlzLCBhY3R1YWxseSwgc29sdmFibGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSB0cmF2ZWxsaW5nIHNhbGVzbWFuIGlzIG9uIGEgbWlzc2lvbiB0byB2aXNpdCBOIGNpdGllcywgZWFjaCBleGFjdGx5IG9uY2UuIFRoZSBjaXRpZXMgYXJlIHJlcHJlc2VudGVkIGJ5IG51bWJlcnMgMSwgMiwgLi4uLCBOLiBXaGF0IHdlIGtub3cgaXMgdGhlIGRpcmVjdCBmbGlnaHQgZHVyYXRpb24gYmV0d2VlbiBlYWNoIHBhaXIgb2YgY2l0aWVzLiBUaGUgc2FsZXNtYW4sIGJlaW5nIHRoZSBlZmZpY2llbnQgbWFuIHRoYXQgaGUgaXMsIHdhbnRzIHRvIG1vZGlmeSB0aGUgY2l0eSB2aXNpdGluZyBzZXF1ZW5jZSBzbyB0aGF0IHRoZSB0b3RhbCBmbGlnaHQgZHVyYXRpb24gaXMgdGhlIG1pbmltdW0gcG9zc2libGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFsYXMsIGFsbCBpcyBub3Qgc28gc2ltcGxlLiBJbiBhZGRpdGlvbiwgdGhlIHNhbGVzbWFuIGhhcyBhIHBlY3VsaWFyIGNvbmRpdGlvbiByZWdhcmRpbmcgdGhlIHNlcXVlbmNlLiBGb3IgZWFjaCBjaXR5IGxhYmVsZWQgSyBtdXN0IGFwcGx5OiBlaXRoZXIgYWxsIGNpdGllcyB3aXRoIGxhYmVscyBzbWFsbGVyIHRoYW4gSyBoYXZlIGJlZW4gdmlzaXRlZCBiZWZvcmUgdGhlIGNpdHkgbGFiZWxlZCBLIG9yIHRoZXkgd2lsbCBhbGwgYmUgdmlzaXRlZCBhZnRlciB0aGUgY2l0eSBsYWJlbGVkIEsuIEluIG90aGVyIHdvcmRzLCB0aGUgc2l0dWF0aW9uIHdoZW4gb25lIG9mIHN1Y2ggY2l0aWVzIGlzIHZpc2l0ZWQgYmVmb3JlLCBhbmQgdGhlIG90aGVyIGFmdGVyIGlzIG5vdCBhbGxvd2VkLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Bc3Npc3QgdGhlIHBvb3IgZmVsbG93IGluIGhpcyBhbWJpdGlvdXMgbWlzc2lvbiBhbmQgY2FsY3VsYXRlIHRoZSBtaW5pbXVtIHRvdGFsIGZsaWdodCBkdXJhdGlvbiBuZWVkZWQgaW4gb3JkZXIgdG8gdHJhdmVsIHRvIGFsbCB0aGUgY2l0aWVzLCBzdGFydGluZyBmcm9tIHdoaWNoZXZlciBhbmQgZW5kaW5nIGluIHdoaWNoZXZlciBjaXR5LCB2aXNpdGluZyBldmVyeSBjaXR5IGV4YWN0bHkgb25jZSwgc28gdGhhdCBoaXMgcGVjdWxpYXIgcmVxdWVzdCBpcyBmdWxmaWxsZWQuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgcG9zaXRpdmUgaW50ZWdlciBOICgyICZsZTsgTiAmbGU7IDE1MDApLCB0aGUgbnVtYmVyIG9mIGNpdGllcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgTiBwb3NpdGl2ZSBpbnRlZ2VycyBmcm9tIHRoZSBpbnRlcnZhbCBbMCwgMTAwMF0uIFRoZSBudW1iZXIgaW4gQjxzdXA+dGg8XC9zdXA+IHBsYWNlIGluIHRoZSBBPHN1cD50aDxcL3N1cD4gcm93IHJlcHJlc2VudHMgdGhlIGZsaWdodCBkdXJhdGlvbiBiZXR3ZWVuIGNpdGllcyBBIGFuZCBCOyB0aGF0IG51bWJlciBpcyBlcXVhbCB0byB0aGUgQTxzdXA+dGg8XC9zdXA+IG51bWJlciBpbiB0aGUgQjxzdXA+dGg8XC9zdXA+IHJvdy4gV2hlbiBBID0gQiwgdGhhdCBudW1iZXIgaXMgMC4gT3RoZXJ3aXNlLCBpdCBpcyBhIHBvc2l0aXZlIHZhbHVlLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIHJlcXVpcmVkIG1pbmltdW0gdG90YWwgZmxpZ2h0IGR1cmF0aW9uLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+Q2xhcmlmaWNhdGlvbiBvZiB0aGUgZmlyc3QgZXhhbXBsZTogdGhlIG9wdGltYWwgc2VxdWVuY2UgaXMgMiwgMSwgMyBvciAzLCAxLCAyLiBUaGUgc2VxdWVuY2UgMSwgMywgMiBpcyBldmVuIG1vcmUgZmF2b3VyYWJsZSwgYnV0IGl0IGRvZXMgbm90IGZ1bGZpbGwgdGhlIHNhbGVzbWFuJiMzOTtzIGNvbmRpdGlvbi48XC9wPlxyXG5cclxuPHA+Q2xhcmlmaWNhdGlvbiBvZiB0aGUgc2Vjb25kIGV4YW1wbGU6IHRoZSBzZXF1ZW5jZSBpcyBlaXRoZXIgMywgMSwgMiwgNCBvciA0LCAyLCAxLCAzLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2013/2014 > Contest #2 4번