题目背景

电动车遛城市

描述

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

输入格式

第一行输入 cnt start end

接下来一行输入整数 chargeLen 表示城市数量

接下来一行输入 chargeLen 个整数 表示 charge[i]

接下来一行输入整数 pathLen

接下来 pathLen 行 每行以 [城市 A 编号,城市 B 编号,两城市间距离] 格式输入

输出格式

输出最少需要花费多少单位时间

样例输入1

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

样例输出1

43

样例输入2

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

样例输出2

38

样例解释

1 <= paths.length <= 200

paths[i].length == 3

2 <= charge.length == n <= 100

0 <= path[i][0],path[i][1],start,end < n

1 <= cnt <= 100

1 <= path[i][2] <= cnt

1 <= charge[i] <= 100

题目保证所有城市相互可以到达

---

样例图如下