做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2416. -- [C++一本通-动态规划]例9.5 最短路径

2416: [C++一本通-动态规划]例9.5 最短路径

时间限制: 1 Sec  内存限制: 128 MB
提交: 69  解决: 52
[上一题][提交][讨论版][状态][下一题]

题目描述

下图表示城市之间的交通路网,线段上的数字表示费用,单向通行由A->E。试用动态规划的最优化原理求出A->E的最省费用。

                                  

输入

第1行,输入N,表示有N个城市;第2行到n+1行是各个城市间的距离。(n<=11)

输出

第1行是最短路径长度;接下来1行是最短路径。

样例输入

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

提示

标签

[上一题][提交][讨论版][状态][下一题]