信息学奥赛一本通(C++版)在线评测系统

本网站由成都石室中学、福建长乐一中信奥教练联合呈现。题库教师群:307432527,仅供教师加入
围观:初赛那点事!
提高 普及
你现在还未登录哦!
用户登录
注册新用户

1261:【例9.5】城市交通路网


时间限制: 1000 ms         内存限制: 65536 KB
提交数: 4577     通过数: 3306

【题目描述】

下图表示城市之间的交通路网,线段上的数字表示费用,单向通行由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

提交 统计信息


本题库与《信息学奥赛一本通(C++版)》(科学技术文献出版社)配套,版权及相关事宜请与本书作者联系,本网站不作解答。
本网站属公益、非盈利性质,不涉及与书相关的商业活动,后期可能适当收取费用以支持网站的运行维护。
目前因个人编写水平有限,网站维护、网站安全方面及部分功能的开发尚不成熟,如遇疑问,请通过版主信箱联系。
感谢成都石室中学Wuvin、Qizy、Xehoth三位同学对本网站的支持,特别鸣谢北京师范大学ACM前校队易超、唐巧、洪涛同学。
版主信箱:ybt_mail@126.com