首页 > 试题广场 >

共享单车

[编程题]共享单车
  • 热度指数：1407 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

给出一张图，图上有 n 个节点，从 1 到 n 编号，和 m 条边，每条边有一个权重，表示小明走路通过这条边的时间，所有边都是无向的。

小明从 1 号节点出发，他要去 n 号节点，他想用的总时间尽可能的短。小明有共享单车 APP ，图上有些节点有共享单车，当他到达一个有车节点后，他就可以一直骑车，如果一条边走路通过的时间是 t ，那么骑车通过的时间就是 t/2 ，这里的除法是向下取整，如 t = 1 时 t/2 = 0，t = 2时，t/2 = 1。
小明可以先走到一个节点取车再骑车过去，也可以直接走过去，问他在最优策略下，需要多少时间从 1 到 n。

数据范围：   

输入描述:
第一行两个数 n,m ，接下来有 m 行，每行三个数 u,v,w ，表示 u 和 v 之间有一条边权为 w 的无向边
接下来一个数 k ，表示有 k 个节点有车，最后输入 k 行，表示有车节点的编号
输入的图中可能有自环和重边


输出描述:
输出一个数，从 1 到 n 的最少所需的时间，如果 1 和 n 不连通，输出 -1
示例1

输入

4 3
1 3 1
1 2 3
2 4 4
1
3

输出

4

说明

小明走过去拿到车，然后骑车去目的地，路线入图：
算法知识视频讲解
开通博客
头像 17c89
发表于 2024-01-07 15:24:31
import java.util.Comparator; import java.util.HashSet; import java.util.PriorityQueue; import java.util.Scanner; public class Main { // 当前节点的邻接边 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 bandiaoz
发表于 2024-12-29 01:07:25
解题思路 这是一个最短路径问题，但有以下特殊条件： 图中某些节点有共享单车 如果骑单车，边的权重会变为原来的一半 一旦获得单车就可以一直使用 需要从节点1到达节点 ，如果不可达则输出-1 解决方案： 使用Dijkstra算法的变体 状态需要记录：(节点编号, 是否有单车) 使用优先队列优化 对 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

搜索 图
难度：
2条回答 4268浏览

热门推荐

通过挑战的用户

查看代码

相关试题

共享单车

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号