首页 > 试题广场 >

共享单车

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

给出一张图，图上有 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

说明

小明走过去拿到车，然后骑车去目的地，路线入图：
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

搜索 图
难度：
0条回答 3305浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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