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