题目内容

随着疫情放开，小明准备自驾旅行，旅行中经过的每个城市都有一些朋友需要去探访消费，最近小明有点经济紧张，请帮小明设计一下行驶路线，能用最少的探访费用到达终点。

1、小明的汽车是电车，最多只能行驶$M$公里，且中间城市没有充电桩

2、假如旅行一共有$N$个城市，城市序号分别为$0,1,2，。。。，N-1$，则起点为$0$，终点为$N-1$

题解

题目描述

小明计划自驾旅行，起点为城市编号 0，终点为城市编号 N-1。他需要探访经过的每个城市，并支付相应的消费费用。由于他的汽车是电动车，充满电后最多只能行驶 M 公里，且中途城市没有充电桩，因此整个旅途的单次行驶距离不能超过 M 公里。每两个城市之间可能有道路连接，且行驶需要耗费一定的公里数。

需要设计一条行驶路线，使得在满足行驶距离不超过 M 公里的条件下，从起点到终点的探访费用最少。如果无法到达终点，输出 -1。

思路分析