1261：【例9.5】城市交通路網
【題目描述】
下圖表示城市之間的交通路網，線段上的數字表示費用，單向通行由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
思路：
類似最長上升子序列、矩陣最值，與摘花生、矩陣最大值等題目一樣，都要記錄到能夠到這個點的路徑的最值。與最長上升子序列一樣，每次都要尋找符合條件的最值然後記錄下來，還可以記錄前驅
縮小問題規模：從能夠到達這個點的幾條路徑中尋找最短的路徑。
L（n)=min(L( 能夠到達的點 )）+v(n)值。
1、數組a記錄路徑（鄰接矩陣）
2、數組b記錄幾條路徑之中到達這個點的最短路徑值。一開始初始化為0.
3、數組c記錄到達目标點的最短路徑的前驅點（下标）。也是初始化為0，（是以第一個點的前驅就是v0，即表示沒有前驅）
最後找b[n]即可。
如圖：
代碼：
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
//鄰接矩陣 最短路徑
//思路:打表記錄 從開始到達每一個點的最小路徑 周遊所有能夠到達終點的所有路徑，尋找最小值
//類似最長上升子序列的二維變式
int a[101][101];
int b[101];//記錄所有路徑到達這個點的最短值
int q[101];//記錄前驅
int shuchu[101];
int main()
{
int n;
cin>>n;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(q,0,sizeof(q));
for(int i=1; i<=n;i++)
{
for(int j =1;j<=n;j++)
{
cin>>a[i][j];
}
}
int min_j=99999;
int xiabiao;
for(int j=1;j<=n;j++)//周遊各個終點
{
min_j=99999;
for(int i=1;i<=n;i++)//尋找前驅
{
if(a[i][j]!=0) //能到達
{
a[i][j]=a[i][j]+b[i];//求通過這前驅到達這個點的最短值
if(min_j>a[i][j])//在能夠達到的點路徑中尋找最小值
{
min_j=a[i][j];
xiabiao=i;
}
}
}
if(min_j!=99999) //如果沒有到達這個點的路徑，比如第一個點，就還是按0來計算
{
b[j]=min_j;
q[j]=xiabiao;
}
}
//輸出
printf("minlong=%d\n",b[n]);
int num=0;
int fag=0;
int p=n;
while(q[p])//直到前驅為0
{
num++;//記錄個數
shuchu[num]=q[p];
p=q[p];
}
for(int i=num;i>=1;i--)//倒着輸出
{
if(fag==0)
{
cout<<shuchu[i];
fag=1;
}
else if(fag!=0)
cout<<' '<<shuchu[i];
}
cout<<' '<<n;
return 0;
}