本文主要是介绍DP 城市交通路网，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目描述】
下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由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
【来源】
No
题目分析：
这题比较爽，首先我们要弄清那一堆二维数组的含义，a[i][]代表i城市的的去向距离，a[][j]代表去j城市的距离。
动态规划做这一题，设f[i]为i城市到10城市的最短距离，则f【10】=0，并将其他初始化为10000000。（代码解释原因）
动态转移方程为：f[i]=min(f[i],a[i][x]+f[x]) 条件：f[i]!=1000000,a[i][x]>0,i<x<=n;
代码实现：
#include<bits/stdc++.h>
using namespace std;
int main()
{int i,j,x,a[100][100],f[100],c[100];int n;cin>>n;for(i=1;i<=n;i++)for(j=1;j<=n;j++)cin>>a[i][j]; memset(f,1000000,sizeof(f)); //初始化f和cmemset(c,0,sizeof(c));f[n]=0; //初始f[n]for(i=n-1;i>=1;i--) //从终点逆推for(x=i+1;x<=n;x++) //若f[x]=1000000说明x到终点城市不通if(a[i][x]>0&&f[x]!=1000000&&f[i]>a[i][x]+f[x]){ //a[i][x]>0表示城市i和城市x通路c[i]=x;f[i]=f[x]+a[i][x];cout<<x<<" "<<i<<" "<<f[i]<<endl;}cout<<"minlong="<<f[1]<<endl;x=1;while(x!=0){cout<<x<<" ";x=c[x];}return 0;
}
这篇关于DP 城市交通路网的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
