“我是要成為海賊王的男人！”
路飛他們偉大航路行程的起點(diǎn)是羅格鎮(zhèn)，終點(diǎn)是拉夫德魯（那里藏匿著“唯一的大秘寶”——ONE PIECE）。而航程中間，則是各式各樣的島嶼。
因?yàn)閭ゴ蠛铰飞系臍夂蚴之惓?，所以?lái)往任意兩個(gè)島嶼之間的時(shí)間差別很大，從A島到B島可能需要1天，而從B島到A島則可能需要1年。當(dāng)然，任意兩個(gè)島之間的航行時(shí)間雖然差別很大，但都是已知的。
現(xiàn)在假設(shè)路飛一行從羅格鎮(zhèn)（起點(diǎn)）出發(fā)，遍歷偉大航路中間所有的島嶼（但是已經(jīng)經(jīng)過(guò)的島嶼不能再次經(jīng)過(guò)），最后到達(dá)拉夫德魯（終點(diǎn)）。假設(shè)他們?cè)趰u上不作任何的停留，請(qǐng)問(wèn)，他們最少需要花費(fèi)多少時(shí)間才能到達(dá)終點(diǎn)？
輸入輸入數(shù)據(jù)包含多行。
第一行包含一個(gè)整數(shù)N(2 < N ≤ 16)，代表偉大航路上一共有N個(gè)島嶼（包含起點(diǎn)的羅格鎮(zhèn)和終點(diǎn)的拉夫德魯）。其中，起點(diǎn)的編號(hào)為1，終點(diǎn)的編號(hào)為N。
之后的N行每一行包含N個(gè)整數(shù)，其中，第i(1 ≤ i ≤ N)行的第j(1 ≤ j ≤ N)個(gè)整數(shù)代表從第i個(gè)島嶼出發(fā)到第j個(gè)島嶼需要的時(shí)間t(0 < t < 10000)。第i行第i個(gè)整數(shù)為0。輸出輸出為一個(gè)整數(shù)，代表路飛一行從起點(diǎn)遍歷所有中間島嶼（不重復(fù)）之后到達(dá)終點(diǎn)所需要的最少的時(shí)間。樣例輸入
樣例輸入1： 4 0 10 20 999 5 0 90 30 99 50 0 10 999 1 2 0 樣例輸入2： 5 0 18 13 98 8 89 0 45 78 43 22 38 0 96 12 68 19 29 0 52 95 83 21 24 0
樣例輸出
網(wǎng)友評(píng)論
