题目形容
这是 LeetCode 上的 1786. 从第一个节点登程到最初一个节点的受限门路数 ，难度为 中等。
Tag :「最短路」、「线性 DP」
现有一个加权无向连通图。给你一个正整数 n，示意图中有 n 个节点，并按从 1 到 n 给节点编号；另给你一个数组 edges，其中每个 $edges[i] = [u_{i}, v_{i}, weight_{i}]$ 示意存在一条位于节点 $u_{i}$ 和 $v_{i}$ 之间的边，这条边的权重为 $weight_{i}$。
从节点 start 登程到节点 end 的门路是一个形如 $[z_{0}, z_{1}, z_{2}, …, z_{k}]$ 的节点序列，满足 $z_{0} = 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^9 + 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 \times 10^4$
- $n – 1 <= edges.length <= 4 \times 10^4$
- $edges[i].length == 3$
- $1 <= ui, vi <= n$
- $u_i != v_i$
- $1 <= weighti <= 10^5$
- 任意两个节点之间至少存在一条边
- 任意两个节点之间至多存在一条门路
堆优化 Dijkstra + 动静布局
n 为点的数量，m 为边的数量。
为了不便了解，咱们将第 n 个点称为「终点」，第 1 个点称为「结尾」。
依照题意，咱们须要先求每个点到结尾的「最短路」，求最短路的算法有很多，通常依据「有无负权边」&「浓密图还是稠密图」进行抉择。
该题只有正权变，而且“边”和“点”的数量在一个数量级上，属于稠密图。
因而咱们能够采纳「最短路」算法：堆优化的 Dijkstra，复杂度为 $O(m\log{n})$。
PS. 通常会优先选择 SPFA，SPFA 通常状况下复杂度为 $O(m)$，但最坏状况下复杂度为 $O(n \times m)$。从数据上来说 SPFA 也会超，而且本题还联合了 DP，因而可能会卡掉图论局部的 SPFA。出于这些思考，我间接应用堆优化 Dijkstra。
当咱们求得了每个点到结尾的「最短路」之后，接下来咱们须要求得从「终点」到「结尾」的 受限门路数量。
这显然能够用 DP 来做。
咱们定义 f(i) 为从第 i 个点到结尾的受限门路数量，f(1) 就是咱们的答案，而 f(n) = 1 是一个不言而喻的起始条件。
因为题目的 受限门路数 的定义，咱们须要找的门路所蕴含的点，必须是其间隔结尾的最短路越来越近的。
举个🌰，对于示例 1，其中一条符合要求的门路为 1 --> 2 --> 3 --> 5。
这条门路的搜寻过程能够看做，从结尾（第 5 个点）登程，逆着走，每次抉择一个点（例如 a）之后，再抉择下一个点（例如 b）时就必须 满足最短路间隔比上一个点（点 a）要远，如果最终能选到终点（第一个点），阐明统计出一条无效门路。
咱们的搜寻形式决定了须要先依照最短路间隔进行从小到大排序。
不失一般性，当咱们要求 f(i) 的时候，其实找的是 i 点能够达到的点 j，并且 j 点到结尾的最短路要严格小于 i 点到结尾的最短路。
符合条件的点 j 有很多个，将所有的 f(j) 累加即是 f(i)。
代码：
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];
}
}- 工夫复杂度：求最短路的复杂度为 $O(m\log{n})$，DP 过程坏状况下要扫完所有的边，复杂度为 $O(m)$。整体复杂度为 $O(m\log{n})$
- 空间复杂度：$O(n + m)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.1786 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布