题目描述

小明的电动车电量充满时可行驶距离为 $cnt$，每行驶 1 单位距离消耗 1 单位电量，且花费 1 单位时间。小明想选择电动车作为代步工具。地图上共有 N 个景点，景点编号为 $0 \sim N-1$。他将地图信息以 $[城市 A 编号,城市 B 编号,两城市间距离]$ 格式整理在大小为 $M$ 的二维数组 $paths$，表示城市 A、B 间存在双向通路。初始状态，电动车电量为 0。每个城市都设有充电桩，$charge[i]$ 表示第 i 个城市每充 1 单位电量需要花费的单位时间。请返回小明最少需要花费多少单位时间从起点城市 $start$ 抵达终点城市 $end$。

输入格式

第一行空格隔开的 5 个整数，分别表示 $N,M, cnt, start, end$，意义如题目描述所示；

接下来的 $M$ 行，每行三个空格隔开的整数，表示城市 A 编号，城市 B 编号，两城市间距离；

再接下来一行 $N$ 个空格隔开的整数表示 $charge$ 数组中的各个元素。

输出格式

一行一个整数表示小明最少需要花费多少单位时间从起点城市 $start$ 抵达终点城市 $end$。

示例 1：

4 5 6 1 0
1 3 3
3 2 1
2 1 3
0 1 4
3 0 5
2 10 4 1

43

解释： 最佳路线为：1->3->0。 在城市 1 仅充 3 单位电至城市 3，然后在城市 3 充 5 单位电，行驶至城市 0。 充电用时共 310 + 51= 35 行驶用时 3 + 5 = 8，此时总用时最短 43。

示例 2：

5 6 8 0 2
0 4 2
4 3 5
3 0 5
0 1 5
3 2 4
1 2 8
4 1 1 3 2

38

解释： 最佳路线为：0->4->3->2。 城市 0 充电 2 单位，行驶至城市 4 充电 8 单位，行驶至城市 3 充电 1 单位，最终行驶至城市 2。 充电用时 42+28+3*1 = 27 行驶用时 2+5+4 = 11，总用时最短 38。

提示：

• $1 <= M <= 200$
• $2 <= n <= 100$
• $0 <= A编号,B编号,start,end < n$
• $1 <= cnt <= 100$
• $1 <= 任一两城市之间的距离 <= cnt$
• $1 <= charge[i] <= 100$
• 题目保证所有城市相互可以到达

SOURCE

LCP 35. 电动车游城市