题目描述

一个国家有 $n$ 个城市，城市编号为 $0$ 到 $n - 1$ ，题目保证 所有城市 都由双向道路 连接在一起，共 $m$ 条。道路由二维整数数组 $edges$ 表示，其中 $edges[i] = [x_i, y_i, time_i]$ 表示城市 $x_i$ 和 $y_i$ 之间有一条双向道路，耗费时间为 $time_i$ 分钟。两个城市之间可能会有多条耗费时间不同的道路，但是不会有道路两头连接着同一座城市。

每次经过一个城市时，你需要付通行费。通行费用一个长度为 $n$ 且下标从 0 开始的整数数组 $passingFees$ 表示，其中 $passingFees[j]$ 是你经过城市 $j$ 需要支付的费用。

一开始，你在城市 $0$ ，你想要在 $maxTime$ 分钟以内 （包含 $maxTime$ 分钟）到达城市 $n - 1$ 。旅行的 费用 为你经过的所有城市 通行费之和 （包括 起点和终点城市的通行费）。

给你 $maxTime$，$edges$ 和 $passingFees$ ，请你返回完成旅行的 最小费用 ，如果无法在 $maxTime$ 分钟以内完成旅行，请你返回 $-1$ 。

输入格式

第一行，两个空格隔开的整数表示 $n$，$m$，$maxTime$；

接下来 $m$ 行，每行三个空格隔开的整数，表示 $x_i, y_i, time_i$；

最后一行空格隔开的 $n$ 个整数表示 $passingFees[j]$。

输出格式

一行一个整数表示答案。

示例 1：

6 6 30
0 1 10
1 2 10
2 5 10
0 3 1
3 4 10
4 5 15
5 1 2 20 20 3

11

解释：最优路径为 0 -> 1 -> 2 -> 5 ，总共需要耗费 30 分钟，需要支付 11 的通行费。

示例 2：

6 6 29
0 1 10
1 2 10
2 5 10
0 3 1
3 4 10
4 5 15
5 1 2 20 20 3

48

解释：最优路径为 0 -> 3 -> 4 -> 5 ，总共需要耗费 26 分钟，需要支付 48 的通行费。 你不能选择路径 0 -> 1 -> 2 -> 5 ，因为这条路径耗费的时间太长。

示例 3：

6 6 25
0 1 10
1 2 10
2 5 10
0 3 1
3 4 10
4 5 15
5 1 2 20 20 3

-1

解释：无法在 25 分钟以内从城市 0 到达城市 5 。

提示：

• $1 <= maxTime <= 1000$
• $n == passingFees.length$
• $2 <= n <= 1000$
• $n - 1 <= m == edges.length <= 1000$
• $0 <= x_i, y_i <= n - 1$
• $1 <= time_i <= 1000$
• $1 <= passingFees[j] <= 1000$
• 图中两个节点之间可能有多条路径。
• 图中不含有自环。

source

1928. 规定时间内到达终点的最小花费