解题思路16
需积分: 0 129 浏览量
2022-08-08
21:15:19
上传
评论
收藏 184KB DOCX 举报
过年回家
1 / 3
过年回家
1 题目描述
NowCoder 今年买了一辆新车，他决定自己开车回家过年。回家过程中要经过 n 个大小收费站，
每个收费站的费用不同，你能帮他计算一下最少需要给多少过路费吗？
1.1 输入描述:
输入包含多组数据，每组数据第一行包含两个正整数 m（1≤m≤500）和 n（1≤n≤30），其
中 m 表示接下来输入的行数，n 表示有 n 个收费站，编号依次为 1、2、…、n。出发地的编号为
0，终点的编号为 n，即需要从 0 到 n。
紧接着 m 行，每行包含三个整数 f、t、c，（0≤f, t≤n; 1≤c≤10），分别表示从编号为 f
的地方开到 t，需要交 c 元的过路费。
1.2 输出描述:
对应每组数据，请输出至少需要交多少过路费。
1.3 输入例子:
8 4
0 1 10
0 2 5
1 2 2
1 3 1
2 1 3
2 3 9
2 4 2
3 4 4
1.4 输出例子:
7
2 解题思路
根据题意，可以根据输入构造一个有向图，其中出发地和收费站表示图的顶点，过路费表示有
向边的权重。要求出发地到终点的最少收费，等价于求起点和终点向短路径，可以使用 Dijkstra
代码深渊漫步者
- 粉丝: 14
- 资源: 320
最新资源
- 基于JavaScript讲解的数据结构和算法
- python计算机视觉python-computer-vision.rar
- VB+ACCESS计算机等级考试管理系统(源代码+系统+答辩PPT).zip
- python密码python-ciphers.rar
- 2c60fbb3dt9ad50ed8864298eea1484b.MP4
- 基于yolov8+dlib实现视觉识别的安全驾驶监测系统部署到jetson NX平台源码+模型.zip
- Qt框架+OpenCV+动态爱心+编程教学+520
- 基于opencv+yolov8实现目标追踪及驻留时长统计源码.zip
- 水稻病害基于Yolov8算法优化目标检测识别与AI辅助决策python源码+模型+使用说明.zip
- 海尔618算价表_七海5.20_16.00xlsx(1)(2).xlsx
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论0