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

문제

선주는 자신이 운영하는 N개의 논에 물을 대려고 한다. 물을 대는 방법은 두 가지가 있는데 하나는 직접 논에 우물을 파는 것이고 다른 하나는 이미 물을 대고 있는 다른 논으로부터 물을 끌어오는 법이다.

각각의 논에 대해 우물을 파는 비용과 논들 사이에 물을 끌어오는 비용들이 주어졌을 때 최소의 비용으로 모든 논에 물을 대는 것이 문제이다.

입력

첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어오는데 이는 i번째 논과 j번째 논을 연결하는데 드는 비용 Pi,j(1 ≤ Pi,j ≤ 100,000, Pi,j = Pj,i, Pi,i = 0)를 의미한다.

출력

첫 줄에 모든 논에 물을 대는데 필요한 최소비용을 출력한다.

예제 입력 1

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

예제 출력 1

9
W3sicHJvYmxlbV9pZCI6IjEzNjgiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJiM2NcdWIzMDBcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzEyMFx1YzhmY1x1YjI5NCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVjNmI0XHVjNjAxXHVkNTU4XHViMjk0IE5cdWFjMWNcdWM3NTggXHViMTdjXHVjNWQwIFx1YmIzY1x1Yzc0NCBcdWIzMDBcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWJiM2NcdWM3NDQgXHViMzAwXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWI0NTAgXHVhYzAwXHVjOWMwXHVhYzAwIFx1Yzc4OFx1YjI5NFx1YjM3MCBcdWQ1NThcdWIwOThcdWIyOTQgXHVjOWMxXHVjODExIFx1YjE3Y1x1YzVkMCBcdWM2YjBcdWJiM2NcdWM3NDQgXHVkMzBjXHViMjk0IFx1YWM4M1x1Yzc3NFx1YWNlMCBcdWIyZTRcdWI5NzggXHVkNTU4XHViMDk4XHViMjk0IFx1Yzc3NFx1YmJmOCBcdWJiM2NcdWM3NDQgXHViMzAwXHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWIyZTRcdWI5NzggXHViMTdjXHVjNzNjXHViODVjXHViZDgwXHVkMTMwIFx1YmIzY1x1Yzc0NCBcdWIwNGNcdWM1YjRcdWM2MjRcdWIyOTQgXHViYzk1XHVjNzc0XHViMmU0LjxcL3A+XHJcbjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWIxN2NcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YzZiMFx1YmIzY1x1Yzc0NCBcdWQzMGNcdWIyOTQgXHViZTQ0XHVjNmE5XHVhY2ZjIFx1YjE3Y1x1YjRlNCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViYjNjXHVjNzQ0IFx1YjA0Y1x1YzViNFx1YzYyNFx1YjI5NCBcdWJlNDRcdWM2YTlcdWI0ZTRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YyBcdWNkNWNcdWMxOGNcdWM3NTggXHViZTQ0XHVjNmE5XHVjNzNjXHViODVjIFx1YmFhOFx1YjRlMCBcdWIxN2NcdWM1ZDAgXHViYjNjXHVjNzQ0IFx1YjMwMFx1YjI5NCBcdWFjODNcdWM3NzQgXHViYjM4XHVjODFjXHVjNzc0XHViMmU0LjxcL3A+IiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjE3Y1x1Yzc1OCBcdWMyMTggTigxICZsZTsgTiAmbGU7IDMwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgaVx1YmM4OFx1YzlmOCBcdWIxN2NcdWM1ZDAgXHVjNmIwXHViYjNjXHVjNzQ0IFx1ZDMxNCBcdWI1NGMgXHViNGRjXHViMjk0IFx1YmU0NFx1YzZhOSBXaSgxICZsZTsmbmJzcDtXaSAmbGU7IDEwMCwwMDApXHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWI0ZTRcdWM1YjRcdWM2MjhcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWNcdWIyOTQgXHVhYzAxIFx1YzkwNFx1YzVkMCBOXHVhYzFjXHVjNzU4IFx1YzIxOFx1YWMwMCBcdWI0ZTRcdWM1YjRcdWM2MjRcdWIyOTRcdWIzNzAgXHVjNzc0XHViMjk0IGlcdWJjODhcdWM5ZjggXHViMTdjXHVhY2ZjIGpcdWJjODhcdWM5ZjggXHViMTdjXHVjNzQ0IFx1YzVmMFx1YWNiMFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWI0ZGNcdWIyOTQgXHViZTQ0XHVjNmE5IFBpLGooMSAmbGU7Jm5ic3A7UGksaiAmbGU7IDEwMCwwMDAsIFBpLGogPSBQaixpLCBQaSxpID0gMClcdWI5N2MgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiA8XC9wPiIsIm91dHB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHViYWE4XHViNGUwIFx1YjE3Y1x1YzVkMCBcdWJiM2NcdWM3NDQgXHViMzAwXHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGNcdWJlNDRcdWM2YTlcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+IiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTM2OCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IldhdGVyaW5nIEhvbGUiLCJkZXNjcmlwdGlvbiI6IjxwPkZhcm1lciBKb2huIGhhcyBkZWNpZGVkIHRvIGJyaW5nIHdhdGVyIHRvIGhpcyBOICgxICZsdDs9IE4gJmx0Oz0gMzAwKSBwYXN0dXJlcyB3aGljaCBhcmUgY29udmVuaWVudGx5IG51bWJlcmVkIDEuLk4uIEhlIG1heSBicmluZyB3YXRlciB0byBhIHBhc3R1cmUgZWl0aGVyIGJ5IGJ1aWxkaW5nIGEgd2VsbCBpbiB0aGF0IHBhc3R1cmUgb3IgY29ubmVjdGluZyB0aGUgcGFzdHVyZSB2aWEgYSBwaXBlIHRvIGFub3RoZXIgcGFzdHVyZSB3aGljaCBhbHJlYWR5IGhhcyB3YXRlci48XC9wPlxyXG5cclxuPHA+RGlnZ2luZyBhIHdlbGwgaW4gcGFzdHVyZSBpIGNvc3RzIFdfaSAoMSAmbHQ7PSBXX2kgJmx0Oz0gMTAwLDAwMCkuIENvbm5lY3RpbmcgcGFzdHVyZXMgaSBhbmQgaiB3aXRoIGEgcGlwZSBjb3N0cyBQX2lqICgxICZsdDs9IFBfaWogJmx0Oz0gMTAwLDAwMDsgUF9paiA9IFBfamk7IFBfaWk9MCkuPFwvcD5cclxuXHJcbjxwPkRldGVybWluZSB0aGUgbWluaW11bSBhbW91bnQgRmFybWVyIEpvaG4gd2lsbCBoYXZlIHRvIHBheSB0byB3YXRlciBhbGwgb2YgaGlzIHBhc3R1cmVzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+KiBMaW5lIDE6IEEgc2luZ2xlIGludGVnZXI6IE48XC9wPlxyXG5cclxuPHA+KiBMaW5lcyAyLi5OICsgMTogTGluZSBpKzEgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlcjogV19pPFwvcD5cclxuXHJcbjxwPiogTGluZXMgTisyLi4yTisxOiBMaW5lIE4rMStpIGNvbnRhaW5zIE4gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzOyB0aGUgai10aCBpbnRlZ2VyIGlzIFBfaWo8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4qIExpbmUgMTogQSBzaW5nbGUgbGluZSB3aXRoIGEgc2luZ2xlIGludGVnZXIgdGhhdCBpcyB0aGUgbWluaW11bSBjb3N0IG9mIHByb3ZpZGluZyBhbGwgdGhlIHBhc3R1cmVzIHdpdGggd2F0ZXIuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

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

  • 문제를 번역한 사람: author6