Medium

题目描述

给你一个无向加权连通图。你有一个正整数 n 表示图中有 n 个编号为 1 到 n 的节点，以及一个数组 edges，其中 edges[i] = [ui, vi, weighti] 表示节点 ui 和 vi 之间有一条权重为 weighti 的边。

从节点 start 到节点 end 的路径是一个节点序列 [z0, z1, z2, …, zk]，使得 z0 = start 且 zk = end，并且在 zi 和 zi+1 之间存在一条边，其中 0 <= i <= k-1。

路径的距离是路径上边的权重之和。设 distanceToLastNode(x) 表示节点 n 和节点 x 之间路径的最短距离。受限路径是一条满足 distanceToLastNode(zi) > distanceToLastNode(zi+1) 的路径，其中 0 <= i <= k-1。

返回从节点 1 到节点 n 的受限路径数。由于这个数字可能很大，返回它对 109 + 7 取模的结果。

示例 1：

输入：n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]
输出：3
解释：每个圆圈包含黑色的节点编号和蓝色的 distanceToLastNode 值。三条受限路径是：
1) 1 --> 2 --> 5
2) 1 --> 2 --> 3 --> 5  
3) 1 --> 3 --> 5

示例 2：

输入：n = 7, edges = [[1,3,1],[4,1,2],[7,3,4],[2,5,3],[5,6,1],[6,7,2],[7,5,3],[2,6,4]]
输出：1
解释：每个圆圈包含黑色的节点编号和蓝色的 distanceToLastNode 值。唯一的受限路径是 1 --> 3 --> 7。

提示：

  • 1 <= n <= 2 * 10^4
  • n - 1 <= edges.length <= 4 * 10^4
  • edges[i].length == 3
  • 1 <= ui, vi <= n
  • ui != vi
  • 1 <= weighti <= 10^5
  • 任意两个节点之间最多有一条边
  • 任意两个节点之间至少有一条路径

解题思路

这道题的核心思路是将问题转化为在有向无环图（DAG）上的路径计数问题。

解题步骤：

  1. 计算到最后节点的距离：使用 Dijkstra 算法从节点 n 开始，计算所有节点到节点 n 的最短距离。

  2. 构造有向图：对于每条无向边 [u, v]，如果 distanceToLastNode(u) > distanceToLastNode(v)，则添加有向边 u → v；如果 distanceToLastNode(v) > distanceToLastNode(u)，则添加有向边 v → u。距离相等的边直接丢弃。

  3. 动态规划计数：在构造的 DAG 上，使用记忆化搜索或拓扑排序+DP 计算从节点 1 到节点 n 的路径数量。

关键观察：

  • 受限路径的条件 distanceToLastNode(zi) > distanceToLastNode(zi+1) 确保了我们构造的图是无环的
  • 在有向无环图上计算路径数是经典的动态规划问题

复杂度分析：

  • Dijkstra 算法：O(E log V)
  • 构造有向图：O(E)
  • DP 计数：O(V + E)
  • 总体时间复杂度：O(E log V)

推荐解法： 记忆化搜索，代码简洁且易于理解。

代码实现

class Solution {
public:
    int countRestrictedPaths(int n, vector<vector<int>>& edges) {
        const int MOD = 1e9 + 7;
        
        // 构建邻接表
        vector<vector<pair<int, int>>> graph(n + 1);
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            graph[u].push_back({v, w});
            graph[v].push_back({u, w});
        }
        
        // Dijkstra 计算从节点 n 到所有节点的最短距离
        vector<int> dist(n + 1, INT_MAX);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        dist[n] = 0;
        pq.push({0, n});
        
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (d > dist[u]) continue;
            
            for (auto [v, w] : graph[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }
        
        // 记忆化搜索
        vector<int> memo(n + 1, -1);
        function<int(int)> dfs = [&](int u) -> int {
            if (u == n) return 1;
            if (memo[u] != -1) return memo[u];
            
            int result = 0;
            for (auto [v, w] : graph[u]) {
                if (dist[u] > dist[v]) {
                    result = (result + dfs(v)) % MOD;
                }
            }
            return memo[u] = result;
        };
        
        return dfs(1);
    }
};

class Solution:
    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:
        MOD = 10**9 + 7
        
        # 构建邻接表
        graph = [[] for _ in range(n + 1)]
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))
        
        # Dijkstra 计算从节点 n 到所有节点的最短距离
        dist = [float('inf')] * (n + 1)
        dist[n] = 0
        pq = [(0, n)]
        
        while pq:
            d, u = heappop(pq)
            if d > dist[u]:
                continue
            
            for v, w in graph[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    heappush(pq, (dist[v], v))
        
        # 记忆化搜索
        @lru_cache(maxsize=None)
        def dfs(u):
            if u == n:
                return 1
            
            result = 0
            for v, w in graph[u]:
                if dist[u] > dist[v]:
                    result = (result + dfs(v)) % MOD
            return result
        
        return dfs(1)

public class Solution {
    public int CountRestrictedPaths(int n, int[][] edges) {
        const int MOD = 1000000007;
        
        // 构建邻接表
        List<(int, int)>[] graph = new List<(int, int)>[n + 1];
        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], w = edge[2];
            graph[u].Add((v, w));
            graph[v].Add((u, w));
        }
        
        // Dijkstra 计算从节点 n 到所有节点的最短距离
        int[] dist = new int[n + 1];
        Array.Fill(dist, int.MaxValue);
        dist[n] = 0;
        
        var pq = new PriorityQueue<int, int>();
        pq.Enqueue(n, 0);
        
        while (pq.Count > 0) {
            int u = pq.Dequeue();
            
            foreach (var (v, w) in graph[u]) {
                if (dist[u] != int.MaxValue && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.Enqueue(v, dist[v]);
                }
            }
        }
        
        // 记忆化搜索
        int[] memo = new int[n + 1];
        Array.Fill(memo, -1);
        
        int Dfs(int u) {
            if (u == n) return 1;
            if (memo[u] != -1) return memo[u];
            
            long result = 0;
            foreach (var (v, w) in graph[u]) {
                if (dist[u] > dist[v]) {
                    result = (result + Dfs(v)) % MOD;
                }
            }
            return memo[u] = (int)result;
        }
        
        return Dfs(1);
    }
}

var countRestrictedPaths = function(n, edges) {
    const MOD = 1000000007;
    
    // Build adjacency list
    const graph = Array(n + 1).fill(null).map(() => []);
    for (const [u, v, w] of edges) {
        graph[u].push([v, w]);
        graph[v].push([u, w]);
    }
    
    // Dijkstra to find shortest distances from node n
    const dist = Array(n + 1).fill(Infinity);
    dist[n] = 0;
    const pq = [[0, n]]; // [distance, node]
    
    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, w] of graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push([dist[v], v]);
            }
        }
    }
    
    // DFS with memoization to count restricted paths
    const memo = Array(n + 1).fill(-1);
    
    function dfs(node) {
        if (node === n) return 1;
        if (memo[node] !== -1) return memo[node];
        
        let count = 0;
        for (const [neighbor, _] of graph[node]) {
            if (dist[node] > dist[neighbor]) {
                count = (count + dfs(neighbor)) % MOD;
            }
        }
        
        return memo[node] = count;
    }
    
    return dfs(1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(E log V)，其中 E 是边数，V 是节点数。主要由 Dijkstra 算法决定
空间复杂度O(V + E)，用于存储图的邻接表、距离数组和记忆化数组

相关题目