信息学奥赛一本通 1261:城市交通路网(evd)
发布日期:2022-01-30 02:41:37 浏览次数:21 分类:技术文章

本文共 797 字,大约阅读时间需要 2 分钟。

【题目描述】

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

#include
#include
#include
#include
using namespace std;const int N=105;const int IMAX=9999;int a[N][N],c[N],f[N];int main(){
int n,x; cin>>n; for(int i=1;i<=n;i++) {
f[i]=IMAX; for(int j=1;j<=n;j++) cin>>a[i][j]; } f[n]=0; for(int i=n-1;i>=1;i--) {
for(int j=i+1;j<=n;j++) {
if(a[i][j]&&f[j]+a[i][j]

转载地址:https://blog.csdn.net/everwide1982/article/details/109788634 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:信息学奥赛一本通 1262:挖地雷(evd)
下一篇:信息学奥赛一本通 1263:友好城市(evd)

发表评论

最新留言

很好
[***.229.124.182]2024年03月01日 22时11分05秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

java变量怎么变常量_Java的常量与变量是什么?怎么学习呀? 2019-04-21
java开发招聘试题_客户化开发招聘试题-Java开发.doc 2019-04-21
java jdk win10 1335_win10下安装java jdk,tomcat 2019-04-21
java list二分查找_java中的ArrayList和LinkedList的二分查找速度比 | 学步园 2019-04-21
php中的变量名称用什么表示,PHP变量,方法,类等名称中的有效字符是什么? 2019-04-21
pic32mx是什么cpu_PIC32MX单片机外设库使用(Ⅰ)- 系统时钟及I/O口基本设置 2019-04-21
用c 在mysql上存图片_C 批量保存图片进 mysql 利用MYSQL_BIND插入longblob 2019-04-21
mysql 1045 28000_mysql报关于用户密码1045(28000),几种处理方法 (zhuan) 2019-04-21
solr比mysql的优势_Solr与Elasticsearch的优缺点比较总结和归纳 2019-04-21
华为博士招聘上机考试题目_牛客网-华为-2020届校园招聘上机考试-3 2019-04-21
python中for可以做变量名吗_Python中使用动态变量名的方法 2019-04-21
mysql 日期转换天数_MySQL 日期操作 增减天数、时间转换、时间戳 2019-04-21
java对象去重复_JAVA中List对象去除重复值的方法 2019-04-21
java bss_[转] .bss段和.data段的区别 2019-04-21
java上传图片损坏_大神求助 上传图片后 图片损坏 2019-04-21
java socket唯一标识符_Java Socket编程之常识网络基础知识 2019-04-21
java给xyz大小排序_java递归实现string xyz排序 2019-04-21
mysql 自适应字段宽度_box-sizing解决自适应布局容器宽度问题 2019-04-21
java 配置文件配置路径_Java读取配置文件路径设置 2019-04-21
vux 选择器_vue中的scoped分析以及在element-UI和vux中的应用 2019-04-21