赞
踩
下图表示城市之间的交通路网,线段上的数字表示费用,单向通行由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
- //Created on 2020/2/16
-
- #pragma GCC optimize(2)//请勿随便使用
- #include<bits/stdc++.h>
-
- using namespace std;
-
- const int idata=100+5;
- const int maxn=0x3f3f3f3f;
- int dp[idata][idata];
- int fee[idata*10];
- int show[idata];
- int flag;
-
- int main()
- {
- register int i,j;
- int n;
- cin>>n;
-
- for(i=1;i<=n;i++)
- {
- for(j=1;j<=n;j++)
- {
- cin>>dp[i][j];
- }
- }
- for(i=1;i<n;i++)
- fee[i]=maxn;
-
- fee[n]=0;
- for(i=n-1;i>=1;i--)
- {
- for(j=i+1;j<=n;j++)
- {
- if(dp[i][j]!=0&&fee[j]!=maxn
- &&fee[i]>dp[i][j]+fee[j])
- {
- fee[i]=dp[i][j]+fee[j];
- show[i]=j;
- }
- }
- }
- cout<<"minlong="<<fee[1]<<endl;
-
- flag=1;
- while(flag)
- {
- cout<<flag<<" ";
- flag=show[flag];
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。