城市交通網(動態規劃,最短路徑,輸出最短路徑)

城市交通網(動態規劃,最短路徑,輸出最短路徑)

【例9.5】城市交通路網

時間限制: 1000 ms         記憶體限制: 65536 KB
 

【題目描述】

下圖表示城市之間的交通路網,線段上的數字表示費用,單向通行由A->E。試用動態規劃的最優化原理求出A->E的最省費用。

如圖:求v1到v10的最短路徑長度及最短路徑。

【輸入】

第一行為城市的數量N;

後面是N*N的表示兩個城市間費用組成的矩陣。

【輸出】

A->E的最省費用。

【輸入樣例】

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

【來源】

#include<iostream>
#include<cstring>
#define MAXN 100
using namespace std;
int a[MAXN 5][MAXN 5];//a[i][x]表示vi到vx的最短距離 
int f[MAXN 5];//f[i]表示點vi到v10的最短距離 
int suf[MAXN 5];//suf[i]=x;表示i的字尾節點為x 
int main()
{
memset(a,0,sizeof(a));
memset(suf,0,sizeof(f)); 
int i,x,n;
cin>>n;
for(int i=1;i<=n;i  )
{
for(int x=1;x<=n;x  )
{
cin>>a[i][x];
}
f[i]=100000;
} 
f[n]=0;
for(int i=n-1;i>=1;i--)
{
for(int x=i 1;x<=n;x  )
{
if((a[i][x]>0)&&(f[x]!=100000)&&(f[i]>a[i][x] f[x]))
//如果vi到vx之間有路徑,vx到v10有路徑,並且vi直接到v10的路徑大於通過vx中轉的路徑 
{
f[i]=a[i][x] f[x];
suf[i]=x;//i節點的字尾節點為x 
}
}
}
x=1;
cout<<"minlong="<<f[1]<<endl;
while(x!=0)//模擬迴圈連結串列 
{
cout<<x<<" ";
x=suf[x];
}
cout<<endl;
return 0;
}