欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

第九章 动态规划-1261:【例9.5】城市交通路网

程序员文章站 2022-07-14 21:34:58
...

1261:【例9.5】城市交通路网

时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
下图表示城市之间的交通路网,线段上的数字表示费用,单向通行由A->E。试用动态规划的最优化原理求出A->E的最省费用。
第九章 动态规划-1261:【例9.5】城市交通路网
如图:求v1到v10的最短路径长度及最短路径。

【输入】
第一行为城市的数量N;
后面是N*N的表示两个城市间费用组成的矩阵。

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

【输出】
A->E的最省费用。

minlong=19
1 3 5 8 10


思路:设dp[i][1]=N,表示第i个城市到第1个城市距离边界为N然后从第i个城市开始,对于每个城市每次都遍历所有的点,然后更新距离设dp[i][1]表示第i个城市到第1个城市距离最短时经过的下一个城市然后输出就好了。dp[n][1] 存最短路径.

#include<cstdio>
#include<iostream>
using namespace std; 
const int N = 1000 + 10;
int a[N][N],n,dp[N][3];
int k[N];
void find(int k) //输出入过的各个城市 
{
	if(k != 1) 
	find(dp[k][2]);
	cout << k <<' '; 
}

int main(){
	cin >> n;
	for(int i = 1 ; i <= n; i++)
	 for(int j = 1; j <= n;j++)
	 cin >> a[i][j];        //打印表 
	 for(int i = 2;i <= n;i++)
	 dp[i][1] = N;  //DP边界 
	 k[1] = 1;
	 //计算最短路径
	 for(int i = 2 ; i <= n ;i++)   //第二个城市开始循环
	  {
	  	for(int j = 1 ; j < n; j++)
	  	{
	  		if(a[j][i] != 0) //表示j到i存在通路 
	  		{
	  			if(dp[i][1] > dp[j][1] + a[j][i])
	  			{
	  				dp[i][1] = a[j][i] + dp[j][1]; //城市i 到终点最短距离 
	  				dp[i][2] = j;
				  }
			  }
		  }
	  }
	  printf("minlong=%d\n",dp[n][1]);
	  find(dp[n][2]);
	  cout << n << endl;
	return 0;
}