Formatted question description: https://leetcode.ca/all/882.html

882. Reachable Nodes In Subdivided Graph (Hard)

Starting with an undirected graph (the "original graph") with nodes from 0 to N-1, subdivisions are made to some of the edges.

The graph is given as follows: edges[k] is a list of integer pairs (i, j, n) such that (i, j) is an edge of the original graph,

and n is the total number of new nodes on that edge.

Then, the edge (i, j) is deleted from the original graph, n new nodes (x_1, x_2, ..., x_n) are added to the original graph,

and n+1 new edges (i, x_1), (x_1, x_2), (x_2, x_3), ..., (x_{n-1}, x_n), (x_n, j) are added to the original graph.

Now, you start at node 0 from the original graph, and in each move, you travel along one edge.

Return how many nodes you can reach in at most M moves.

Example 1:

Input: edges = [[0,1,10],[0,2,1],[1,2,2]], M = 6, N = 3
Output: 13
Explanation:
The nodes that are reachable in the final graph after M = 6 moves are indicated below.



Example 2:

Input: edges = [[0,1,4],[1,2,6],[0,2,8],[1,3,1]], M = 10, N = 4
Output: 23

Note:

1. 0 <= edges.length <= 10000
2. 0 <= edges[i][0] < edges[i][1] < N
3. There does not exist any i != j for which edges[i][0] == edges[j][0] and edges[i][1] == edges[j][1].
4. The original graph has no parallel edges.
5. 0 <= edges[i][2] <= 10000
6. 0 <= M <= 10^9
7. 1 <= N <= 3000
8. A reachable node is a node that can be travelled to using at most M moves starting from node 0.

Related Topics:
Heap

Solution 1. Dijkstra

// OJ: https://leetcode.com/problems/reachable-nodes-in-subdivided-graph/
// Time: O(ElogN)
// Space: O(N)
// Ref: https://leetcode.com/problems/reachable-nodes-in-subdivided-graph/solution/
class Solution {
typedef pair<int, int> pii;
public:
int reachableNodes(vector<vector<int>>& edges, int M, int N) {
vector<vector<pii>> G(N);
for (auto &e : edges) {
int u = e[0], v = e[1], w = e[2];
G[u].emplace_back(v, w);
G[v].emplace_back(u, w);
}
map<int, int> dist;
dist[0] = 0;
for (int i = 1; i < N; ++i) dist[i] = M + 1; // M is the maximum steps we can take, so M + 1 is the smallest invalid value.
map<pii, int> used;
int ans = 0;
priority_queue<pii, vector<pii>, greater<pii>> q; // weight, node
q.emplace(0, 0);
while (q.size()) {
auto top = q.top();
q.pop();
int d = top.first, u = top.second;
if (d > dist[u]) continue;
++ans;
for (auto [v, w] : G[u]) {
used[{ u, v }] = min(w, M - d); // M - d is how much further we can walk from this u node
int d2 = d + w + 1; // d2 is the minimal distance from source node to this v node.
if (d2 < min(dist[v], M + 1)) {
q.emplace(d2, v);
dist[v] = d2;
}
}
}
for (auto &e : edges) {
int u = e[0], v = e[1], w = e[2];
ans += min(w, used[{ u, v }] + used[{ v, u }]);
}
return ans;
}
};

• class Solution {
public int reachableNodes(int[][] edges, int M, int N) {
Map<Integer, Map<Integer, Integer>> graphMap = new HashMap<Integer, Map<Integer, Integer>>();
for (int[] edge : edges) {
int node0 = edge[0], node1 = edge[1], insertions = edge[2];
Map<Integer, Integer> map0 = graphMap.getOrDefault(node0, new HashMap<Integer, Integer>());
Map<Integer, Integer> map1 = graphMap.getOrDefault(node1, new HashMap<Integer, Integer>());
map0.put(node1, insertions);
map1.put(node0, insertions);
graphMap.put(node0, map0);
graphMap.put(node1, map1);
}
int[] distances = new int[N];
Arrays.fill(distances, M + 1);
distances[0] = 0;
int[][] used = new int[N][N];
int reachable = 0;
PriorityQueue<int[]> priorityQueue = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] nodeDistance1, int[] nodeDistance2) {
return nodeDistance1[1] - nodeDistance2[1];
}
});
priorityQueue.offer(new int[]{0, 0});
while (!priorityQueue.isEmpty()) {
int[] nodeDistance = priorityQueue.poll();
int node = nodeDistance[0], distance = nodeDistance[1];
if (distance > distances[node])
continue;
reachable++;
if (graphMap.containsKey(node)) {
Map<Integer, Integer> edgesMap = graphMap.get(node);
Set<Integer> keySet = edgesMap.keySet();
for (int adjacent : keySet) {
int currReachable = Math.min(insertions, M - distance);
int newDistance = distance + insertions + 1;
}
}
}
}
for (int[] edge : edges) {
int node0 = edge[0], node1 = edge[1], insertions = edge[2];
reachable += Math.min(insertions, used[node0][node1] + used[node1][node0]);
}
return reachable;
}
}

############

class Solution {
public int reachableNodes(int[][] edges, int maxMoves, int n) {
List<int[]>[] g = new List[n];
Arrays.setAll(g, e -> new ArrayList<>());
for (var e : edges) {
int u = e[0], v = e[1], cnt = e[2] + 1;
}
int[] dist = new int[n];
Arrays.fill(dist, 1 << 30);
PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[0] - b[0]);
q.offer(new int[] {0, 0});
dist[0] = 0;
while (!q.isEmpty()) {
var p = q.poll();
int d = p[0], u = p[1];
for (var nxt : g[u]) {
int v = nxt[0], cnt = nxt[1];
if (d + cnt < dist[v]) {
dist[v] = d + cnt;
q.offer(new int[] {dist[v], v});
}
}
}
int ans = 0;
for (int d : dist) {
if (d <= maxMoves) {
++ans;
}
}
for (var e : edges) {
int u = e[0], v = e[1], cnt = e[2];
int a = Math.min(cnt, Math.max(0, maxMoves - dist[u]));
int b = Math.min(cnt, Math.max(0, maxMoves - dist[v]));
ans += Math.min(cnt, a + b);
}
return ans;
}
}

• // OJ: https://leetcode.com/problems/reachable-nodes-in-subdivided-graph/
// Time: O(ElogE)
// Space: O(E)
// Ref: https://leetcode.com/problems/reachable-nodes-in-subdivided-graph/solution/
class Solution {
public:
int reachableNodes(vector<vector<int>>& E, int maxMoves, int n) {
vector<vector<pair<int, int>>> G(n);
for (auto &e : E) {
int u = e[0], v = e[1], w = e[2];
G[u].emplace_back(v, w);
G[v].emplace_back(u, w);
}
vector<int> step(n, -1);
step[0] = maxMoves;
priority_queue<pair<int, int>> pq; // Max heap. Each entry is (stepsLeft, nodeIndex)
pq.emplace(maxMoves, 0);
int ans = 0;
while (pq.size()) {
auto [stepsLeft, u] = pq.top();
pq.pop();
if (stepsLeft < step[u]) continue;
++ans;
if (stepsLeft == 0) continue;
for (auto &[v, w] : G[u]) {
if (step[v] < stepsLeft - w - 1) {
step[v] = stepsLeft - w - 1;
pq.emplace(step[v], v);
}
}
}
for (auto &e : E) ans += min(e[2], max(0, step[e[0]]) + max(0, step[e[1]]));
return ans;
}
};

• class Solution:
def reachableNodes(self, edges: List[List[int]], maxMoves: int, n: int) -> int:
g = defaultdict(list)
for u, v, cnt in edges:
g[u].append((v, cnt + 1))
g[v].append((u, cnt + 1))
q = [(0, 0)]
dist = [0] + [inf] * n
while q:
d, u = heappop(q)
for v, cnt in g[u]:
if (t := d + cnt) < dist[v]:
dist[v] = t
q.append((t, v))
ans = sum(d <= maxMoves for d in dist)
for u, v, cnt in edges:
a = min(cnt, max(0, maxMoves - dist[u]))
b = min(cnt, max(0, maxMoves - dist[v]))
ans += min(cnt, a + b)
return ans


• func reachableNodes(edges [][]int, maxMoves int, n int) (ans int) {
g := make([][]pair, n)
for _, e := range edges {
u, v, cnt := e[0], e[1], e[2]+1
g[u] = append(g[u], pair{cnt, v})
g[v] = append(g[v], pair{cnt, u})
}
dist := make([]int, n)
for i := range dist {
dist[i] = 1 << 30
}
dist[0] = 0
q := hp{ {0, 0} }
for len(q) > 0 {
p := heap.Pop(&q).(pair)
d, u := p.v, p.i
for _, nxt := range g[u] {
v, cnt := nxt.i, nxt.v
if t := d + cnt; t < dist[v] {
dist[v] = t
heap.Push(&q, pair{t, v})
}
}
}
for _, d := range dist {
if d <= maxMoves {
ans++
}
}
for _, e := range edges {
u, v, cnt := e[0], e[1], e[2]
a := min(cnt, max(0, maxMoves-dist[u]))
b := min(cnt, max(0, maxMoves-dist[v]))
ans += min(cnt, a+b)
}
return
}

type pair struct{ v, i int }
type hp []pair

func (h hp) Len() int            { return len(h) }
func (h hp) Less(i, j int) bool  { return h[i].v < h[j].v }
func (h hp) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

func max(a, b int) int {
if a > b {
return a
}
return b
}

func min(a, b int) int {
if a < b {
return a
}
return b
}