城市交通网（动态规划，最短路径，输出最短路径）

分手后的思念是犯贱 2022-06-08 07:00 350阅读 0赞

### 【例9.5】城市交通路网 ###

时间限制: 1000 ms 内存限制: 65536 KB

### 【题目描述】 ###

下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A->E。试用动态规划的最优化原理求出A->E的最省费用。

![1287.gif][]

如图：求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

### 【来源】 ###

![20170918202141121][]

#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;
    }

[1287.gif]: /images/20220608/2d7683910ca944ffadb092d33b4ce011.png
[20170918202141121]: /images/20220608/2b7dd11ecefa4dd386893c9b8c29a116.png