从第一个节点出发到最后一个节点的受限路径数

1786. 从第一个节点出发到最后一个节点的受限路径数

现有一个加权无向连通图。给你一个正整数 n ，表示图中有 n 个节点，并按从 1 到 n 给节点编号；另给你一个数组 edges ，其中每个 edges[i] = [u_i, v_i, weight_i] 表示存在一条位于节点 u_i 和 v_i 之间的边，这条边的权重为 weight_i 。

从节点 start 出发到节点 end 的路径是一个形如 [z₀, z₁,z₂, ..., z_k] 的节点序列，满足 z₀= start 、z_k = end 且在所有符合 0 <= i <= k-1 的节点 z_i 和 z_i+1 之间存在一条边。

路径的距离定义为这条路径上所有边的权重总和。用 distanceToLastNode(x) 表示节点 n 和 x 之间路径的最短距离。受限路径 为满足 distanceToLastNode(z_i) > distanceToLastNode(z_i+1) 的一条路径，其中 0 <= i <= k-1 。

返回从节点 1 出发到节点 n 的 受限路径数 。由于数字可能很大，请返回对 10⁹ + 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⁴
n - 1 <= edges.length <= 4 * 10⁴
edges[i].length == 3
1 <= u_i, v_i <= n
u_i!= v_i
1 <= weight_i <= 10⁵
任意两个节点之间至多存在一条边
任意两个节点之间至少存在一条路径

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int countRestrictedPaths(int n, vector<vector<int>>& edges) { } };

golang 解法, 执行用时: 404 ms, 内存消耗: 21.9 MB, 提交时间: 2023-10-25 23:52:39

var graph []map[int]int

func countRestrictedPaths(n int, edges [][]int) int {
	graph = make([]map[int]int, n+1)
	dis := networkDelayTime(edges, n, n)
	dp := make([]int, n+1)
	dp[n] = 1
	minHeap := &IntHeap{}
	heap.Push(minHeap, [2]int{dis[n], n})
	dic := map[int]bool{}
	for (*minHeap).Len() > 0 {
		// 优先队列，每次都将 dis 值最小的点取出来
		x := heap.Pop(minHeap).([2]int)
		for i := range graph[x[1]] {
			if dis[i] > x[0] && dis[i] <= dis[1] {
				// 比 dis[1] 大的值没有意义，因为不可能符合受限路径条件，加==号是因为需要计算dp[1]+=
				dp[i] += dp[x[1]]
				dp[i] %= 1000000007
				if dis[i] < dis[1] && !dic[i] {
					dic[i] = true
					// 防止重复加入队列
					heap.Push(minHeap, [2]int{dis[i], i})
				}
			}
		}

	}
	return dp[1]
}
// 先套用 [743].网络延迟时间 的代码，将返回值改成 dis 切片
func networkDelayTime(times [][]int, n int, k int) []int {

	for i := range graph {
		graph[i] = map[int]int{}
	}
	for _, i := range times {
		graph[i[0]][i[1]] = i[2]
		graph[i[1]][i[0]] = i[2]
	}
	minHeap := &IntHeap{}
	dis := make([]int, n+1)
	for i := range dis {
		dis[i] = math.MaxInt32
	}
	dis[k] = 0
	for i := 1; i <= n; i++ {
		heap.Push(minHeap, [2]int{dis[i], i})
	}
	dic := map[int]bool{}
	for (*minHeap).Len() > 0 {
		x := heap.Pop(minHeap).([2]int)
		if dic[x[1]] {
			continue
		}
		dic[x[1]] = true
		for i := range graph[x[1]] {
			if dis[x[1]]+graph[x[1]][i] < dis[i] {
				dis[i] = dis[x[1]] + graph[x[1]][i]
				heap.Push(minHeap, [2]int{dis[i], i})
			}
		}
	}

	return dis
}

type IntHeap [][2]int

func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	*h = append(*h, x.([2]int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

cpp 解法, 执行用时: 464 ms, 内存消耗: 147.9 MB, 提交时间: 2023-10-25 23:50:56

using PII = pair<int, int>;

class Solution {
public:
    int countRestrictedPaths(int n, vector<vector<int>>& edges) {
        g.resize(n+1), mdmap.resize(n+1, INT_MAX), ansmap.resize(n+1, -1);
        // create edge
        for (auto& e : edges) {
            int u = e[0], v = e[1], d = e[2];     
            g[u].push_back({v, d});
            g[v].push_back({u, d});
        }
        
        // create min distance map
        priority_queue<PII, vector<PII>, greater<PII>> pq;
        pq.push({0, n});
        mdmap[n] = 0;
        while (!pq.empty()) {
            auto curr = pq.top(); pq.pop();
            int x = curr.second, sum = curr.first;
            for (auto& nxt : g[x]) {
                int xn = nxt.first, dist = nxt.second;
                if (dist + sum < mdmap[xn]) {
                    pq.push({sum + dist, xn});
                    mdmap[xn] = dist + sum;
                }
            }
        }
        
        return memoSearch(n);
    }
private:
    int mod = pow(10, 9) + 7;
    vector<int> mdmap, ansmap;
    vector<vector<PII>> g; // graph
    
    // memo search (dfs) for the restricted paths
    int memoSearch(int i) {
        if (i == 1) return 1;
        int curr_md = mdmap[i];
        if (ansmap[i] != -1) return ansmap[i];
        
        int ans = 0;
        for (auto& nxt : g[i]) {
            int ni = nxt.first;
            int md = mdmap[ni];
            if (md <= curr_md) continue;
            ans = (ans + memoSearch(ni)) % mod;
        }
        
        ansmap[i] = ans;
        return ans;
    }
};

python3 解法, 执行用时: 416 ms, 内存消耗: 54 MB, 提交时间: 2023-10-25 23:50:28

class Solution:
    def countRestrictedPaths(self, n: int, edges: List[List[int]]) -> int:
        edge = defaultdict(dict)                #既是邻接矩阵，又是邻接表
        for x,y,weight in edges:
            edge[x][y] = weight
            edge[y][x] = weight
        #n为源点，dijkstra单源最短路径,n到各点的最短距离，就是各点到n的最短距离
        dist = [float('inf') for _ in range(n + 1)]
        dist[n] = 0
        visited = set()
        minHeap = [(0, n)]
        while minHeap:
            cloestDist, cloestNode = heapq.heappop(minHeap) #距离源节点最近的结点
            if cloestNode in visited:           #已经在选中的区域里了，就不要再选了
                continue
            visited.add(cloestNode)             #未选择的点中，这是最小的。正式加入区域
            for nxt in edge[cloestNode].keys():      #更新与它相连接的点
                if dist[cloestNode] + edge[cloestNode][nxt] < dist[nxt]:
                    dist[nxt] = dist[cloestNode] + edge[cloestNode][nxt]
                    heapq.heappush(minHeap, (dist[nxt], nxt))              #有更小的了，就进minHeap
        #动态规划 dp  更多的是一种贪心！！！！！！！！！
        dp = [0 for _ in range(n + 1)]
        dp[n] = 1
        a = [node for node in range(1, n + 1)]
        a.sort(key = lambda x: dist[x])

        for node in a:
            for nxt in edge[node].keys():
                if dist[node] > dist[nxt]:
                    dp[node] += dp[nxt]

            if node == 1:   #a中右侧的点，距离都比1的远了，1的最短路径不可能经过他们到达n
                break
        
        return dp[1] % (10**9 + 7)

cpp 解法, 执行用时: 1100 ms, 内存消耗: 216.6 MB, 提交时间: 2023-10-25 23:50:06

class Solution {
public:
    int countRestrictedPaths(int n, vector<vector<int>>& edges) {
        unordered_map<int, unordered_map<int, int>> edge;   //用字典 及时邻接矩阵，又当邻接表用
        for (auto v: edges)
        {
            int x = v[0],   y = v[1],   weight = v[2];
            edge[x][y] = weight;
            edge[y][x] = weight;
        }
        // dijkstra 单源最短路径 n为源点，一次dijkstra,要是从各点出发就麻烦了
        vector<long long> dist(n + 1, INT_MAX);
        dist[n] = (long long)0;                                    //重要的初始化！！！！！！！！！！！！！！
        unordered_set<int> visited;
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> minHeap;
        minHeap.emplace(0, n);
        while (minHeap.size())
        {
            auto [closetDist, closetNode] = minHeap.top();  minHeap.pop();
            visited.insert(closetNode);                     //从待选的点中，选最近的那个
            for (auto [nxt, weight]: edge[closetNode])                 //与其邻接的点
            {
                if (visited.count(nxt) == 0)                //还没加进区域的，就进堆待选
                {
                    if (dist[closetNode] + edge[closetNode][nxt] < dist[nxt])   //入队时判断。其实出堆时判断也行。
                    {
                        dist[nxt] = dist[closetNode] + edge[closetNode][nxt];
                        minHeap.emplace(dist[nxt], nxt);    //有变动，就进堆
                    }
                }
            }
        }
        //贪心 + 动态规划dp
        vector<long long> dp(n + 1, 0);
        dp[n] = (long long)1;                                      //dp中最难把握的初始化
        vector<int> a;
        for (int x = 1; x < n + 1; x ++)
            a.push_back(x);
        sort(a.begin(), a.end(), [&](int x, int y){return dist[x] < dist[y];} );
        for (int node: a)
        {
            for (auto [nxt, weight]: edge[node])
            {
                if (dist[node] > dist[nxt])
                {
                    dp[node] += dp[nxt];
                    dp[node] %= 1000000007;         //感谢评论区一位大佬的提醒。每一步都取余，不然会溢出
                }
            }
            if (node == 1)                      //比1的距离还大的点。1的最短路径一定不会经过他们
                break;
        }
        return dp[1] % 1000000007;
    }
};

java 解法, 执行用时: 187 ms, 内存消耗: 69.6 MB, 提交时间: 2023-10-25 23:49:33

class Solution {
    int mod = 1000000007;
    public int countRestrictedPaths(int n, int[][] es) {
        // 预处理所有的边权。 a b w -> a : { b : w } + b : { a : w }
        Map<Integer, Map<Integer, Integer>> map = new HashMap<>(); 
        for (int[] e : es) {
            int a = e[0], b = e[1], w = e[2];
            Map<Integer, Integer> am = map.getOrDefault(a, new HashMap<Integer, Integer>());
            am.put(b, w);
            map.put(a, am);
            Map<Integer, Integer> bm = map.getOrDefault(b, new HashMap<Integer, Integer>());
            bm.put(a, w);
            map.put(b, bm);
        }

        // 堆优化 Dijkstra：求 每个点 到 第n个点 的最短路
        int[] dist = new int[n + 1];
        boolean[] st = new boolean[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[n] = 0;
        Queue<int[]> q = new PriorityQueue<int[]>((a, b)->a[1]-b[1]); // 点编号，点距离。根据点距离从小到大
        q.add(new int[]{n, 0});
        while (!q.isEmpty()) {
            int[] e = q.poll();
            int idx = e[0], cur = e[1];
            if (st[idx]) continue;
            st[idx] = true;
            Map<Integer, Integer> mm = map.get(idx);
            if (mm == null) continue;
            for (int i : mm.keySet()) {
                dist[i] = Math.min(dist[i], dist[idx] + mm.get(i));
                q.add(new int[]{i, dist[i]});
            }
        }

        // dp 过程
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) arr[i] = new int[]{i + 1, dist[i + 1]}; // 点编号，点距离
        Arrays.sort(arr, (a, b)->a[1]-b[1]); // 根据点距离从小到大排序

        // 定义 f(i) 为从第 i 个点到结尾的受限路径数量
        // 从 f[n] 递推到 f[1]
        int[] f = new int[n + 1]; 
        f[n] = 1;
        for (int i = 0; i < n; i++) {
            int idx = arr[i][0], cur = arr[i][1];
            Map<Integer, Integer> mm = map.get(idx);
            if (mm == null) continue;
            for (int next : mm.keySet()) {
                if (cur > dist[next]) {
                    f[idx] += f[next];
                    f[idx] %= mod;
                }
            }
            // 第 1 个节点不一定是距离第 n 个节点最远的点，但我们只需要 f[1]，可以直接跳出循环
            if (idx == 1) break;
        }
        return f[1];
    }
}

上一题

下一题

详情