题解

题目描述

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

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

思路分析

题目内容

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

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

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

3、每个城市游玩需要费用为$fees = [f0,f1,f2,f3...]$，每项费用$f>=0$，总费用包括$fees[0]$和$fees[N-1]$

4、每两个城市之间耗电通过{$i,j,k$}标识从i到j或者从$j$到$i$是可以相互到达的，并且需要耗电$k$公里，未定义的视为不可到达

输入描述

第一行:汽车最大可行驶距离$M(0<M<=1000)$

第二行:城市数量$N(1<N<=1000)$，及每个城市的消费费用

第三行:城市间联通关系数量$K$

后续$K$行:$i\ j\ k$表示到或者$j$到$i$需要耗电$k$公里

输出描述

可达:输出最少的探访费用

不可达:输出$-1$

样例1

输入

500
4 1000 3000 4000 2000
5
0 1 200
0 3 250
1 3 300
0 2 150 
2 3 250

输出

3000

说明

最优路径为$0->3$，总共需要耗电$250$公里，需要支付费用$3000$

样例2

输入

400
4 1000 3000 4000 2000
4 
0 1 200
1 3 300
0 2 150
2 3 250

输出

7000