共计 4005 个字符,预计需要花费 11 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 882. 细分图中的可达到节点 ,难度为 艰难。
Tag :「最短路」、「单源最短路」、「Dijkstra」、「SPFA」
给你一个无向图(原始图),图中有 n
个节点,编号从 0
到 n - 1
。你决定将图中的每条边 细分 为一条节点链,每条边之间的新节点数各不相同。
图用由边组成的二维数组 edges
示意,其中 $edges[i] = [u_{i}, v_{i}, cnt_{i}]$ 示意原始图中节点 $u_{i}$ 和 $v_{i}$ 之间存在一条边,$cnt_{i}$ 是将边 细分 后的新节点总数。留神,$cnt_{i} = 0$ 示意边不可细分。
要 细分边 $[u_{i}, v_{i}]$,须要将其替换为 $(cnt_{i} + 1)$ 条新边,和 $cnt_{i}$ 个新节点。新节点为 $x_1, x_2, …, x_{cnt_{i}}$,新边为 $[u_{i}, x_{1}], [x_{1}, x_{2}], [x_{2}, x_{3}], …, [x_{cnt_{i}}+1, x_{cnt_{i}}], [x_{cnt_{i}}, v_{i}]$。
当初失去一个 新的细分图,请你计算从节点 0
登程,能够达到多少个节点?如果节点间间隔是 maxMoves
或更少,则视为 能够达到。
给你原始图和 maxMoves
,返回 新的细分图中从节点 0
登程 可达到的节点数。
示例 1:
输出:edges = [[0,1,10],[0,2,1],[1,2,2]], maxMoves = 6, n = 3
输入:13
解释:边的细分状况如上图所示。能够达到的节点曾经用黄色标注进去。
示例 2:
输出:edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], maxMoves = 10, n = 4
输入:23
示例 3:
输出:edges = [[1,2,4],[1,4,5],[1,3,1],[2,3,4],[3,4,5]], maxMoves = 17, n = 5
输入:1
解释:节点 0 与图的其余部分没有连通,所以只有节点 0 能够达到。
提醒:
- $0 <= edges.length <= \min(n * (n – 1) / 2, 10^4)$
- $edges[i].length = 3$
- $0 <= u_{i} < v_{i} < n$
- 图中 不存在平行边
- $0 <= cnt_{i} <= 10^4$
- $0 <= maxMoves <= 10^9$
- $1 <= n <= 3000$
奢侈 Dijkstra
为了不便,咱们将原始图边的数量记为 m
,因而对于原始图而言,点的数量 $3000$,边的数量为 $10000$。
题目要咱们求新图上,从 0
点登程可达到的点的数量,咱们将原图上存在的点称为「原点」,细分边上减少的点称为「细分点」,两类点中可达点的数量即是答案。
在别离思考如何统计两类点之前,咱们须要从新定义一下边的权重:若原点 u
和原点 v
的边上存在 c
个细分点,咱们将原点 u
和原点 v
之间的边看作是一条权重为 c + 1
的无向边(联合题意,c
个点存在 c + 1
个分段 / 间隔)。
从新定义边的权重后,因为该图是「浓密图」,咱们能够应用「奢侈 Dijkstra」来求解最短路,失去 $dist$ 数组,其中 $dist[x] = t$ 含意为从原点 0
点登程,达到原点 x
的最短距离为 t
。
不理解最短路的同学能够看前置 🧀 : 涵盖所有的「存图形式」与「最短路算法(详尽正文)」
随后思考如何统计答案(可达点的数量),依据统计点的类型分状况探讨:
- 对于原点:若有 $dist[x] < max$ 的话,阐明原点
x
可达,累加到答案中; - 对于细分点:因为所有的细分点都在原图边上,因而咱们能够统计所有原图边上有多少细分点可达。
对于任意一条边 $e(u, v)$ 而言,该边上可达点数量蕴含「通过原点u
可达」以及「通过原点v
可达」的交加,其中原点0
达到原点u
以及原点v
的间隔,咱们是已知的。因而通过原点u
可达的数量为 $\max(0, max – dist[u])$,通过原点v
可达的数量为 $\max(0, max – dist[v])$,两者之和与该边上细分点的总数取min
即是这条边可达点的数量。
代码:
class Solution {
static int N = 3010, INF = 0x3f3f3f3f;
static int[][] g = new int[N][N];
static int[] dist = new int[N];
static boolean[] vis = new boolean[N];
public int reachableNodes(int[][] edges, int max, int n) {
// 建图
for (int i = 0; i < n; i++) Arrays.fill(g[i], INF);
for (int[] info : edges) {int a = info[0], b = info[1], c = info[2] + 1;
g[a][b] = g[b][a] = c;
}
// 奢侈 Dijkstra
Arrays.fill(dist, INF);
Arrays.fill(vis, false);
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++) dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
}
// 统计答案
int ans = 0;
for (int i = 0; i < n; i++) {if (dist[i] <= max) ans++;
}
for (int[] info : edges) {int a = info[0], b = info[1], c = info[2];
int c1 = Math.max(0, max - dist[a]), c2 = Math.max(0, max - dist[b]);
ans += Math.min(c, c1 + c2);
}
return ans;
}
}
- 工夫复杂度:建图复杂度为 $O(m)$;应用奢侈 Dijkstra 求最短路复杂度为 $O(n^2)$;统计答案复杂度为 $O(n + m)$。整体复杂度为 $O(m + n^2)$
- 空间复杂度:$O(n^2)$
SPFA
从数据范畴来看,无论是奢侈 Dijkstra 还是堆优化版的 Dijkstra 都能够过,复杂度别离为 $O(n^2)$ 和 $O(m\log{n})$。
那 Bellman Ford 类的单源最短路就无奈通过了吗?
实践上,无论是 Bellman Ford 还是 SPFA 复杂度均为 $O(n \times m)$,均无奈通过本题。但实际上 SPFA 因为应用队列对松弛程序进行了调整,因而在应答「非菊花图」时均体现良好,复杂度可视为 $O(k \times m)$,近似 $O(m)$。
代码:
class Solution {
static int N = 3010, M = 20010, INF = 0x3f3f3f3f, idx = 0;
static int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
static int[] dist = new int[N];
static boolean[] vis = new boolean[N];
void add(int a, int b, int c) {e[idx] = b;
ne[idx] = he[a];
w[idx] = c;
he[a] = idx++;
}
public int reachableNodes(int[][] edges, int max, int n) {
// 建图
Arrays.fill(he, -1);
idx = 0;
for (int[] info : edges) {int a = info[0], b = info[1], c = info[2] + 1;
add(a, b, c); add(b, a, c);
}
// SPFA
Arrays.fill(dist, INF);
Arrays.fill(vis, false);
Deque<Integer> d = new ArrayDeque<>();
d.addLast(0);
dist[0] = 0;
vis[0] = true;
while (!d.isEmpty()) {int t = d.pollFirst();
vis[t] = false;
for (int i = he[t]; i != -1; i = ne[i]) {int j = e[i];
if (dist[j] > dist[t] + w[i]) {dist[j] = dist[t] + w[i];
if (vis[j]) continue;
d.addLast(j);
vis[j] = true;
}
}
}
// 统计答案
int ans = 0;
for (int i = 0; i < n; i++) {if (dist[i] <= max) ans++;
}
for (int[] info : edges) {int a = info[0], b = info[1], c = info[2];
int c1 = Math.max(0, max - dist[a]), c2 = Math.max(0, max - dist[b]);
ans += Math.min(c, c1 + c2);
}
return ans;
}
}
- 工夫复杂度:建图复杂度为 $O(m)$;应用 SPFA 求最短路复杂度为 $O(n \times m)$;统计答案复杂度为 $O(n + m)$。整体复杂度为 $O(n \times m)$
- 空间复杂度:$O(n + m)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.882
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先把所有不带锁的题目刷完。
在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSou…。
在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布