Medium

题目描述

给你一个整数 n 和一个有向图，图中有 n 个节点，编号从 0 到 n - 1。图用二维数组 edges 表示，其中 edges[i] = [ui, vi, starti, endi] 表示从节点 ui 到 vi 的一条边，该边只能在满足 starti <= t <= endi 的整数时间 t 使用。

你在时间 0 从节点 0 开始。

在一个时间单位内，你可以：

  • 在当前节点等待而不移动，或
  • 如果当前时间 t 满足 starti <= t <= endi，沿着从当前节点出发的边移动。

返回到达节点 n - 1 所需的最少时间。如果不可能到达，返回 -1。

示例 1：

输入：n = 3, edges = [[0,1,0,1],[1,2,2,5]]
输出：3
解释：
最优路径是：
- 在时间 t = 0，使用边 (0 → 1)，该边在时间 0 到 1 可用。在时间 t = 1 到达节点 1，然后等待到 t = 2。
- 在时间 t = 2，使用边 (1 → 2)，该边在时间 2 到 5 可用。在时间 3 到达节点 2。
因此，到达节点 2 的最少时间是 3。

示例 2：

输入：n = 4, edges = [[0,1,0,3],[1,3,7,8],[0,2,1,5],[2,3,4,7]]
输出：5

示例 3：

输入：n = 3, edges = [[1,0,1,3],[1,2,3,5]]
输出：-1
解释：
由于节点 0 没有出边，无法到达节点 2。因此输出 -1。

约束条件：

  • 1 <= n <= 10^5
  • 0 <= edges.length <= 10^5
  • edges[i] == [ui, vi, starti, endi]
  • 0 <= ui, vi <= n - 1
  • ui != vi
  • 0 <= starti <= endi <= 10^9

解题思路

这是一个带有时间约束的最短路径问题，需要使用修改版的 Dijkstra 算法来解决。

核心思路：

  1. 状态定义：使用 (节点, 到达时间) 作为状态，而不是传统的只考虑节点
  2. 时间约束处理：对于边 [u, v, start, end]，如果当前时间 t 满足：
    • t > end：无法使用这条边
    • start <= t <= end：可以立即使用，到达时间为 t + 1
    • t < start：需要等待到时间 start，到达时间为 start + 1

算法步骤：

  1. 构建邻接表存储图的边信息
  2. 使用优先队列（最小堆）进行 Dijkstra 搜索，状态为 (到达时间, 节点)
  3. 对于每个节点的每条出边，根据时间约束计算下一个状态的到达时间
  4. 使用访问数组避免重复访问相同的 (节点, 时间) 状态

优化点：

  • 由于时间可能很大，我们不能用二维数组记录所有状态
  • 使用 set 或 map 来记录访问过的状态
  • 当第一次到达目标节点时，由于使用最小堆，这就是最优解

时间复杂度： O(E log V)，其中 E 是边数，V 是节点数 空间复杂度： O(V + E)

代码实现

class Solution {
public:
    int minTime(int n, vector<vector<int>>& edges) {
        vector<vector<vector<int>>> graph(n);
        
        // 构建邻接表
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1], start = edge[2], end = edge[3];
            graph[u].push_back({v, start, end});
        }
        
        // 优先队列：{时间, 节点}
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        set<pair<int, int>> visited; // {节点, 时间}
        
        pq.push({0, 0});
        
        while (!pq.empty()) {
            auto [time, node] = pq.top();
            pq.pop();
            
            if (node == n - 1) {
                return time;
            }
            
            if (visited.count({node, time})) {
                continue;
            }
            visited.insert({node, time});
            
            // 遍历所有出边
            for (auto& edge : graph[node]) {
                int nextNode = edge[0], start = edge[1], end = edge[2];
                
                int arrivalTime;
                if (time > end) {
                    continue; // 无法使用这条边
                } else if (time >= start) {
                    arrivalTime = time + 1; // 立即使用
                } else {
                    arrivalTime = start + 1; // 等待到start时间
                }
                
                if (!visited.count({nextNode, arrivalTime})) {
                    pq.push({arrivalTime, nextNode});
                }
            }
        }
        
        return -1;
    }
};

class Solution:
    def minTime(self, n: int, edges: List[List[int]]) -> int:
        from collections import defaultdict
        import heapq
        
        # 构建邻接表
        graph = defaultdict(list)
        for u, v, start, end in edges:
            graph[u].append((v, start, end))
        
        # 优先队列：(时间, 节点)
        pq = [(0, 0)]
        visited = set()
        
        while pq:
            time, node = heapq.heappop(pq)
            
            if node == n - 1:
                return time
            
            if (node, time) in visited:
                continue
            visited.add((node, time))
            
            # 遍历所有出边
            for next_node, start, end in graph[node]:
                if time > end:
                    continue  # 无法使用这条边
                elif time >= start:
                    arrival_time = time + 1  # 立即使用
                else:
                    arrival_time = start + 1  # 等待到start时间
                
                if (next_node, arrival_time) not in visited:
                    heapq.heappush(pq, (arrival_time, next_node))
        
        return -1

public class Solution {
    public int MinTime(int n, int[][] edges) {
        var graph = new List<(int, int, int)>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<(int, int, int)>();
        }
        
        // 构建邻接表
        foreach (var edge in edges) {
            int u = edge[0], v = edge[1], start = edge[2], end = edge[3];
            graph[u].Add((v, start, end));
        }
        
        // 优先队列：(时间, 节点)
        var pq = new PriorityQueue<(int, int), int>();
        var visited = new HashSet<(int, int)>();
        
        pq.Enqueue((0, 0), 0);
        
        while (pq.Count > 0) {
            var (time, node) = pq.Dequeue();
            
            if (node == n - 1) {
                return time;
            }
            
            if (visited.Contains((node, time))) {
                continue;
            }
            visited.Add((node, time));
            
            // 遍历所有出边
            foreach (var (nextNode, start, end) in graph[node]) {
                int arrivalTime;
                if (time > end) {
                    continue; // 无法使用这条边
                } else if (time >= start) {
                    arrivalTime = time + 1; // 立即使用
                } else {
                    arrivalTime = start + 1; // 等待到start时间
                }
                
                if (!visited.Contains((nextNode, arrivalTime))) {
                    pq.Enqueue((arrivalTime, nextNode), arrivalTime);
                }
            }
        }
        
        return -1;
    }
}

var minTime = function(n, edges) {
    const graph = Array(n).fill().map(() => []);
    
    for (const [u, v, start, end] of edges) {
        graph[u].push([v, start, end]);
    }
    
    const pq = new MinPriorityQueue({ priority: x => x[0] });
    pq.enqueue([0, 0]);
    const dist = Array(n).fill(Infinity);
    dist[0] = 0;
    
    while (!pq.isEmpty()) {
        const [time, node] = pq.dequeue().element;
        
        if (node === n - 1) return time;
        if (time > dist[node]) continue;
        
        for (const [neighbor, start, end] of graph[node]) {
            let arrivalTime;
            if (time <= end) {
                arrivalTime = Math.max(time, start) + 1;
            } else {
                continue;
            }
            
            if (arrivalTime < dist[neighbor]) {
                dist[neighbor] = arrivalTime;
                pq.enqueue([arrivalTime, neighbor]);
            }
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(E log V)E 是边数，V 是节点数。每条边最多被处理一次，每次操作涉及优先队列的插入/删除
空间复杂度O(V + E)存储图的邻接表需要 O(V + E)，优先队列和访问集合在最坏情况下需要 O(V) 空间