这是 LeetCode 上的「1976. 到达目的地的方案数」,难度为「中等」。
Tag : 「最短路」、「拓扑排序」、「动态规划」
你在一个城市里,城市由
个路口组成,路口编号为
到
,某些路口之间有 双向 道路。输入保证你可以从任意路口出发到达其他任意路口,且任意两个路口之间最多有一条路。
给你一个整数 n
和二维整数数组 roads
,其中
表示在路口
和
之间有一条需要花费
时间才能通过的道路。你想知道花费 最少时间 从路口
出发到达路口
的方案数。
请返回花费 最少时间 到达目的地的 路径数目 。由于答案可能很大,将结果对
取余 后返回。
示例 1:
输入:n = 7, roads = [[0,6,7],[0,1,2],[1,2,3],[1,3,3],[6,3,3],[3,5,1],[6,5,1],[2,5,1],[0,4,5],[4,6,2]]
输出:4
解释:从路口 0 出发到路口 6 花费的最少时间是 7 分钟。
四条花费 7 分钟的路径分别为:
- 0 ➝ 6
- 0 ➝ 4 ➝ 6
- 0 ➝ 1 ➝ 2 ➝ 5 ➝ 6
- 0 ➝ 1 ➝ 3 ➝ 5 ➝ 6
示例 2:
输入:n = 2, roads = [[1,0,10]]
输出:1
解释:只有一条从路口 0 到路口 1 的路,花费 10 分钟。
提示:
roads.length
为了方便,我们记 roads
为 rs
,令点数为 n
,边数为 m
。
边数与点数不在一个数量级上(
),属于「稠密图」,我们可以使用「邻接矩阵」进行存图,同时使用朴素 Dijkstra
求解从
号点到其他点的最短路,记为 dist
数组,
代表以
号点为起点到到
点的最短路径为
。
当我们预处理出
点到其他点的最短距离后,考虑如何统计从
点到
点,且路径和为
的方案数。
一个容易想到的性质:在任意的合法方案中,途径的该路径中的每个点时,都是以最短路径的方式到达的。
使用「反证法」证明该性质的正确性:假设其中一条合法路径为 a -> ... -> k -> ... -> z
(其中 a
为
号点,z
为
号点),其为合法路径,意味着从 a
到 z
的路径和为
。若我们在经过某个途经点,假设为 k
时,所途径的路径总和
不是
的话,意味着我们可以调整从 a
到 k
的路径,使其变为
,而后续路径不变(从 k
到 z
的路径不变)来得到一条路径和比
要小的从 a
到 z
的路径,这与
为从 a
到 z
的最短路冲突。
至此,我们证明了「在任意的合法方案中,途径的该路径中的每个点时,都是以最短路径的方式到达的」这一性质。
利用该性质,我们可以对图进行「重建」,对于原图中点
与点
权重为
的无向边,我们根据
、
和
三者关系建立有向边,并统计入度:
,在新图上增加从
到
的权重为
的有向边,同时
入度加一;
,在新图上增加从
到
的权重为
的有向边,同时
入度加一。
构建新图的目的是能够在跑「拓扑排序」过程中进行 DP
,统计方案数。
定义
为从
到达
点的方案数,
为答案,同时我们有显而易见的初始化条件
。
不失一般性考虑
如何计算,若我们存在一条从
到
的出边,并且
已确定更新完成(通过判断
的入度是为
得知,入度为
意味着已经没有其他状态可以更新
),我们可以用
来更新
,即有
,含义将到达
的路径数累加到到达
的路径数中,同时更新
的入度。
代码:
class Solution {
int N = 210, MOD = (int)1e9+7;
long INF = (long)1e12;
int[][] g = new int[N][N];
int[] in = new int[N];
long[] dist = new long[N];
boolean[] vis = new boolean[N];
int n;
public int countPaths(int _n, int[][] rs) {
n = _n;
for (int[] info : rs) {
int a = info[0], b = info[1], c = info[2];
g[a][b] = g[b][a] = c;
}
// 朴素 Dijkstra 求解从 0 点到其他点的最短路
dijkstra();
// 利用最短路重新建图,并统计入度
for (int[] info : rs) {
int a = info[0], b = info[1], c = info[2];
g[a][b] = g[b][a] = 0;
if (dist[a] + c == dist[b]) {
g[a][b] = c; in[b]++;
} else if (dist[b] + c == dist[a]) {
g[b][a] = c; in[a]++;
}
}
// 跑拓扑排序统计方案数
Deque<Integer> d = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
if (in[i] == 0) d.addLast(i);
}
int[] f = new int[n];
f[0] = 1;
while (!d.isEmpty()) {
int x = d.pollFirst();
for (int i = 0; i < n; i++) {
if (g[x][i] == 0) continue;
f[i] += f[x];
f[i] %= MOD;
if (--in[i] == 0) d.addLast(i);
}
}
return f[n - 1];
}
void dijkstra() {
Arrays.fill(dist, INF);
dist[0] = 0;
for (int i = 0; i < n; i++) {
int t = -1;
for (int j = 0; j < n; j++) {
if (!vis[j] && (t == -1 || dist[j] < dist[t])) t = j;
}
vis[t] = true;
for (int j = 0; j < n; j++) {
if (g[t][j] == 0) continue;
dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
}
}
}
}
;Dijkstra 求最短路复杂度为
;再次建图复杂度为
,跑拓扑排序统计方案数复杂度为
。整体复杂度为
这是我们「刷穿 LeetCode」系列文章的第 No.1976
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。