Hard

题目描述

给定一个有向无环图，包含 n 个节点，编号从 0 到 n - 1。图由长度为 m 的二维数组 edges 表示，其中 edges[i] = [ui, vi, costi] 表示从节点 ui 到节点 vi 的单向通信，恢复成本为 costi。

一些节点可能处于离线状态。给定一个布尔数组 online，其中 online[i] = true 表示节点 i 在线。节点 0 和 n - 1 始终在线。

从 0 到 n - 1 的路径是有效的，当且仅当：

  • 路径上的所有中间节点都在线
  • 路径上所有边的总恢复成本不超过 k

对于每条有效路径，定义其分数为该路径上最小边成本。

返回所有有效路径中的最大路径分数（即最大的最小边成本）。如果不存在有效路径，返回 -1。

示例 1：

输入：edges = [[0,1,5],[1,3,10],[0,2,3],[2,3,4]], online = [true,true,true,true], k = 10
输出：3
解释：
从节点 0 到节点 3 有两条可能的路径：
- 路径 0 → 1 → 3：总成本 = 5 + 10 = 15，超过 k，无效
- 路径 0 → 2 → 3：总成本 = 3 + 4 = 7 ≤ k，有效，最小边成本 = min(3, 4) = 3

示例 2：

输入：edges = [[0,1,7],[1,4,5],[0,2,6],[2,3,6],[3,4,2],[2,4,6]], online = [true,true,true,false,true], k = 12
输出：6
解释：
节点 3 离线，经过节点 3 的路径无效。
有效路径：
- 路径 0 → 1 → 4：总成本 = 12，最小边成本 = 5
- 路径 0 → 2 → 4：总成本 = 12，最小边成本 = 6
最大路径分数为 6

约束条件：

  • n == online.length
  • 2 ≤ n ≤ 5 × 10^4
  • 0 ≤ m ≤ min(10^5, n × (n - 1) / 2)
  • 0 ≤ ui, vi < n
  • ui ≠ vi
  • 0 ≤ costi ≤ 10^9
  • 0 ≤ k ≤ 5 × 10^13
  • online[0] 和 online[n-1] 都为 true
  • 给定图是有向无环图

解题思路

这是一道结合二分搜索和最短路径算法的题目。核心思路如下：

问题转化： 我们要找最大的路径分数，其中路径分数定义为路径上最小边权。这提示我们可以用二分搜索答案。

二分搜索策略：

  • 二分搜索可能的答案范围（最小边权的最大值）
  • 对于每个候选值 mid，检查是否存在有效路径，其中所有边权都 ≥ mid，且总成本 ≤ k

检查函数实现： 由于图是 DAG，我们可以使用两种方法：

  1. Dijkstra 算法：在只包含边权 ≥ mid 的子图上运行
  2. 动态规划 + 拓扑排序：利用 DAG 性质，按拓扑顺序计算最短路径

算法流程：

  1. 收集所有边权作为二分搜索的候选答案
  2. 二分搜索最大可能的最小边权
  3. 对每个 mid 值，构建包含边权 ≥ mid 且连接在线节点的子图
  4. 在子图上运行最短路径算法，检查从 0 到 n-1 的最短路径是否 ≤ k

推荐使用 Dijkstra 算法，因为它更直观且容易实现。

代码实现

class Solution {
public:
    int findMaxPathScore(vector<vector<int>>& edges, vector<bool>& online, long long k) {
        int n = online.size();
        
        // 收集所有边权作为候选答案
        set<int> costs;
        for (auto& edge : edges) {
            costs.insert(edge[2]);
        }
        
        vector<int> candidates(costs.begin(), costs.end());
        sort(candidates.rbegin(), candidates.rend()); // 降序排列
        
        for (int cost : candidates) {
            if (canReach(edges, online, k, cost, n)) {
                return cost;
            }
        }
        
        return -1;
    }
    
private:
    bool canReach(vector<vector<int>>& edges, vector<bool>& online, long long k, int minCost, int n) {
        // 构建子图：只包含权重 >= minCost 且连接在线节点的边
        vector<vector<pair<int, int>>> graph(n);
        
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1], cost = edge[2];
            if (cost >= minCost && online[u] && online[v]) {
                graph[u].push_back({v, cost});
            }
        }
        
        // Dijkstra 算法
        vector<long long> dist(n, LLONG_MAX);
        priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
        
        dist[0] = 0;
        pq.push({0, 0});
        
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            
            if (d > dist[u]) continue;
            
            for (auto [v, cost] : graph[u]) {
                long long newDist = dist[u] + cost;
                if (newDist < dist[v]) {
                    dist[v] = newDist;
                    pq.push({newDist, v});
                }
            }
        }
        
        return dist[n-1] <= k;
    }
};

class Solution:
    def findMaxPathScore(self, edges: List[List[int]], online: List[bool], k: int) -> int:
        import heapq
        
        n = len(online)
        
        # 收集所有边权作为候选答案
        costs = sorted(set(edge[2] for edge in edges), reverse=True)
        
        def can_reach(min_cost):
            # 构建子图：只包含权重 >= min_cost 且连接在线节点的边
            graph = [[] for _ in range(n)]
            
            for u, v, cost in edges:
                if cost >= min_cost and online[u] and online[v]:
                    graph[u].append((v, cost))
            
            # Dijkstra 算法
            dist = [float('inf')] * n
            dist[0] = 0
            pq = [(0, 0)]
            
            while pq:
                d, u = heapq.heappop(pq)
                
                if d > dist[u]:
                    continue
                
                for v, cost in graph[u]:
                    new_dist = dist[u] + cost
                    if new_dist < dist[v]:
                        dist[v] = new_dist
                        heapq.heappush(pq, (new_dist, v))
            
            return dist[n-1] <= k
        
        for cost in costs:
            if can_reach(cost):
                return cost
        
        return -1

public class Solution {
    public int FindMaxPathScore(int[][] edges, bool[] online, long k) {
        int n = online.Length;
        
        // 收集所有边权作为候选答案
        var costs = new HashSet<int>();
        foreach (var edge in edges) {
            costs.Add(edge[2]);
        }
        
        var candidates = costs.ToList();
        candidates.Sort((a, b) => b.CompareTo(a)); // 降序排列
        
        foreach (int cost in candidates) {
            if (CanReach(edges, online, k, cost, n)) {
                return cost;
            }
        }
        
        return -1;
    }
    
    private bool CanReach(int[][] edges, bool[] online, long k, int minCost, int n) {
        // 构建子图
        var graph = new List<(int, int)>[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new List<(int, int)>();
        }
        
        foreach (var edge in edges) {
            int u = edge[0], v = edge[1], cost = edge[2];
            if (cost >= minCost && online[u] && online[v]) {
                graph[u].Add((v, cost));
            }
        }
        
        // Dijkstra 算法
        var dist = new long[n];
        Array.Fill(dist, long.MaxValue);
        var pq = new PriorityQueue<(long dist, int node), long>();
        
        dist[0] = 0;
        pq.Enqueue((0, 0), 0);
        
        while (pq.Count > 0) {
            var (d, u) = pq.Dequeue();
            
            if (d > dist[u]) continue;
            
            foreach (var (v, cost) in graph[u]) {
                long newDist = dist[u] + cost;
                if (newDist < dist[v]) {
                    dist[v] = newDist;
                    pq.Enqueue((newDist, v), newDist);
                }
            }
        }
        
        return dist[n-1] <= k;
    }
}

var findMaxPathScore = function(edges, online, k) {
    const n = online.length;
    
    // 收集所有边权作为候选答案
    const costs = [...new Set(edges.map(edge => edge[2]))];
    costs.sort((a, b) => b - a); // 降序排列
    
    function canReach(minCost) {
        // 构建子图
        const graph = Array(n).fill().map(() => []);
        
        for (const [u, v, cost] of edges) {
            if (cost >= minCost && online[u] && online[v]) {
                graph[u].push([v, cost]);
            }
        }
        
        // Dijkstra 算法
        const dist = Array(n).fill(Infinity);
        const pq = [[0, 0]]; // [distance, node]
        dist[0] = 0;
        
        while (pq.length > 0) {
            pq.sort((a, b) => a[0] - b[0]);
            const [d, u] = pq.shift();
            
            if (d > dist[u]) continue;
            
            for (const [v, cost] of graph[u]) {
                const newDist = dist[u] + cost;
                if (newDist < dist[v]) {
                    dist[v] = newDist;
                    pq.push([newDist, v]);
                }
            }
        }
        
        return dist[n-1] <= k;
    }
    
    for (const cost of costs) {
        if (canReach(cost)) {
            return cost;
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度分析
时间复杂度O(E × (V log V + E))，其中 E 是边数，V 是节点数。需要对每个不同的边权运行一次 Dijkstra 算法
空间复杂度O(V + E)，用于存储图结构和 Dijkstra 算法的辅助数组