1261：【例9.5】城市交通路网
时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由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
1. #include <stdlib.h> 2. #include <cstdio> 3. #include <algorithm> 4. #include <iostream> 5. using namespace std; 6. const int M=105; 7. int a[M][M],f[M],c[M];//f记录最短距离 c记录下个位置点 8. int main() 9. { 10. int i,j,n,x; 11. cin>>n; 12. for(i=1;i<=n;i++){ 13. for(j=1;j<=n;j++) cin>>a[i][j]; 14. f[i]=1000000; 15. } 16. f[n]=0; 17. for(i=n-1;i>=1;i--) 18. for(x=i+1;x<=n;x++) 19. if(a[i][x]>0 &&(f[x]!=1000000 && f[i]>a[i][x]+f[x])){ 20. f[i]=a[i][x]+f[x]; 21. c[i]=x; 22. } 23. cout<<"minlong="<<f[1]<<endl; 24. x=1; 25. while(x!=0){ 26. cout<<x<<' ';x=c[x]; 27. } 28. cout<<endl; 29. //for(i=1;i<=n;i++) cout<<"f["<<i<<"]:"<<f[i]<<" c["<<i<<"]:"<<c[i]<<endl; 30. //system("pause"); 31. return 0; 32. }
