第九章 动态规划-1261:【例9.5】城市交通路网
程序员文章站
2022-07-14 21:34:58
...
1261:【例9.5】城市交通路网
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
下图表示城市之间的交通路网,线段上的数字表示费用,单向通行由A->E。试用动态规划的最优化原理求出A->E的最省费用。
如图:求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;
}