题目：
一个国家有 n 个城市，城市编号为 0 到 n - 1 ，题目保证 所有城市 都由双向道路 连接在一起 。道路由二维整数数组 edges 表示，其中 edges[i] = [xi, yi, timei] 表示城市 xi 和 yi 之间有一条双向道路，耗费时间为 timei 分钟。两个城市之间可能会有多条耗费时间不同的道路，但是不会有道路两头连接着同一座城市。
每次经过一个城市时，你需要付通行费。通行费用一个长度为 n 且下标从 0 开始的整数数组 passingFees 表示，其中 passingFees[j] 是你经过城市 j 需要支付的费用。
一开始，你在城市 0 ，你想要在 maxTime 分钟以内 （包含 maxTime 分钟）到达城市 n - 1 。旅行的 费用 为你经过的所有城市 通行费之和 （包括 起点和终点城市的通行费）。
给你 maxTime，edges 和 passingFees ，请你返回完成旅行的 最小费用 ，如果无法在 maxTime 分钟以内完成旅行，请你返回 -1 。
示例 1：
输入：maxTime = 30, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
输出：11
解释：最优路径为 0 -> 1 -> 2 -> 5 ，总共需要耗费 30 分钟，需要支付 11 的通行费。
示例 2：
输入：maxTime = 29, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
输出：48
解释：最优路径为 0 -> 3 -> 4 -> 5 ，总共需要耗费 26 分钟，需要支付 48 的通行费。
你不能选择路径 0 -> 1 -> 2 -> 5 ，因为这条路径耗费的时间太长。
示例 3：
输入：maxTime = 25, edges = [[0,1,10],[1,2,10],[2,5,10],[0,3,1],[3,4,10],[4,5,15]], passingFees = [5,1,2,20,20,3]
输出：-1
解释：无法在 25 分钟以内从城市 0 到达城市 5 。
提示：
1 <= maxTime <= 1000n == passingFees.length2 <= n <= 1000n - 1 <= edges.length <= 10000 <= xi, yi <= n - 11 <= timei <= 10001 <= passingFees[j] <= 1000- 图中两个节点之间可能有多条路径。
- 图中不含有自环。
思路：
问题描述：我们需要找到一条从城市 0 到城市 n - 1 的路径，使得总花费最小，并且整个旅程的时间不超过 maxTime 分钟。总花费定义为经过所有城市的通行费之和。
解决方案：为了达到这个目标，我们可以采用动态规划结合深度优先搜索（DFS）的方法，并使用记忆化技术来避免重复计算。
数据结构：
邻接表 (graph): 用于存储图的信息。每个节点的邻居以及到达邻居所需的时间。
动态规划数组 (dp): 用于存储从任意节点到达目标节点 n - 1 在特定时间内的最小花费。dp[i][t] 表示从节点 i 出发，在时间 t 时到达节点 n - 1 的最小花费。初始值设为 INT_MAX，表示未计算过或不可达。
算法步骤：
初始化:
创建一个大小为 (n * (maxTime + 1)) 的 dp 数组，其中 n 是城市数量，maxTime 是允许的最大时间。
初始化图的邻接表 graph。
深度优先搜索 (dfs):
对于每个节点，尝试访问它的所有邻居。
对于每个邻居，计算到达该邻居所需的时间是否小于或等于剩余时间。
如果时间允许，递归地调用 dfs 函数，并将邻居节点的最小成本加上当前节点的成本，更新 dp 数组。
记忆化:
在访问某个节点及其时间状态时，如果该状态已经被计算过，则直接返回存储的结果。
这样可以减少重复计算，提高算法效率。
边界条件处理:
当时间不足到达邻居时，返回 -1。
当到达目标节点 n - 1 时，返回该节点的成本。
返回结果:
从起点 0 开始调用 dfs 函数，并返回从起点出发在 maxTime 时间内到达终点的最小成本。如果无法到达，则返回 -1。
关键点：
记忆化搜索：避免重复计算相同的状态。
动态规划：利用 dp 数组存储已解决子问题的结果。
边界条件处理：正确处理边界情况，如时间不足或到达目标节点。
代码：
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
class Solution {
public:
int minCost(int maxTime, vector<vector<int>>& edges, vector<int>& passingFees) {
int n = passingFees.size();
// dp[i][t] 表示到达 i 节点，在时间 t 时的最小花费
vector<vector<int>> dp(n, vector<int>(maxTime + 1, INT_MAX));
// 使用邻接表来表示图
vector<vector<pair<int, int>>> graph(n);
for (auto& edge : edges) {
int x = edge[0], y = edge[1], t = edge[2];
graph[x].emplace_back(y, t);
graph[y].emplace_back(x, t);
}
// 记忆化搜索
function<int(int, int)> dfs = [&](int node, int time) -> int {
// 如果时间不足以到达任何邻居，则返回 -1
if (time < 0) return -1;
if (node == n - 1) return passingFees[node]; // 目标节点
if (dp[node][time] != INT_MAX) return dp[node][time]; // 已经计算过的情况
int minCost = INT_MAX;
for (auto [neighbor, cost] : graph[node]) {
if (cost <= time) { // 只有当剩余时间足够到达邻居节点时才考虑这条边
int next_time = time - cost;
int costToNeighbor = dfs(neighbor, next_time);
if (costToNeighbor >= 0) { // 确保邻居节点也是可达的
minCost = min(minCost, passingFees[node] + costToNeighbor);
}
}
}
dp[node][time] = (minCost == INT_MAX) ? -1 : minCost;
return dp[node][time];
};
int result = dfs(0, maxTime);
return result;
}
};