題目 3049:
城市交通路網(wǎng)
時(shí)間限制: 2s
內(nèi)存限制: 192MB 提交: 319 解決: 81
題目描述
下圖表示城市之間的交通路網(wǎng)，線段上的數(shù)字表示費(fèi)用，單向通行由A->E。試用動(dòng)態(tài)規(guī)劃的最優(yōu)化原理求出A->E的最省費(fèi)用。
如圖：求v1到v10的最短路徑長(zhǎng)度及最短路徑。
輸入格式
第一行為城市的數(shù)量N;
后面是N*N的表示兩個(gè)城市間費(fèi)用組成的矩陣。
后面是N*N的表示兩個(gè)城市間費(fèi)用組成的矩陣。
輸出格式
A->E的最省費(fèi)用。
樣例輸入
10 0 2 5 1 0 0 0 0 0 0 0 0 0 0 12 14 0 0 0 0 0 0 0 0 6 10 4 0 0 0 0 0 0 0 13 12 11 0 0 0 0 0 0 0 0 0 0 3 9 0 0 0 0 0 0 0 0 6 5 0 0 0 0 0 0 0 0 0 10 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0
樣例輸出
minlong=19 1 3 5 8 10
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情