882. Reachable Nodes In Subdivided Graph
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:
0 <= edges.length <= 10000
0 <= edges[i][0] < edges[i][1] < N
- There does not exist any
i != j
for whichedges[i][0] == edges[j][0]
andedges[i][1] == edges[j][1]
. - The original graph has no parallel edges.
0 <= edges[i][2] <= 10000
0 <= M <= 10^9
1 <= N <= 3000
- A reachable node is a node that can be travelled to using at most M moves starting from node 0.
Approach #1: C++. [graph/heap]
class Solution { public: int reachableNodes(vector<vector<int>>& edges, int M, int N) { unordered_map<int, unordered_map<int, int>> g; for (const auto& edge : edges) { g[edge[0]][edge[1]] = g[edge[1]][edge[0]] = edge[2]; } priority_queue<pair<int, int>> q; // HP : node unordered_map<int, int> HP; // node : HP q.push({M, 0}); while (!q.empty()) { int hp = q.top().first; int cur = q.top().second; q.pop(); if (HP.count(cur)) continue; HP[cur] = hp; for (const auto& pair : g[cur]) { int nxt = pair.first; int nxt_hp = hp - pair.second - 1; if (HP.count(nxt) || nxt_hp < 0) continue; q.push({nxt_hp, nxt}); } } int ans = HP.size(); for (const auto& e : edges) { int uv = HP.count(e[0]) ? HP[e[0]] : 0; int vu = HP.count(e[1]) ? HP[e[1]] : 0; ans += min(e[2], uv + vu); } return ans; } };
Analysis:
https://zxi.mytechroad.com/blog/graph/leetcode-882-reachable-nodes-in-subdivided-graph/
相关文章
- Lintcode: Route Between Two Nodes in Graph
- win7环境下,vagrant,在启动虚拟机的时候报错io.rb:32:in `encode': incomplete "xC8" on GBK (Encoding::InvalidByteSequenceError)
- java线程共享受限资源 解决资源竞争 thinking in java4 21.3
- DENIED Redis is running in protected mode because protected mode is enabled
- [转]mysql问题解决SELECT list is not in GROUP BY clause and contains nonaggregated column
- PDO drivers no value in Windows
- nginx: [emerg] bind() to 0.0.0.0:443 failed(98:Address already in use)解决方法
- was cached in the local repository, resolution will not be reattempted until the update interval of fintech has elapsed or updates are forced
- The operation names in the portType match the method names in the SEI or Web service implementation class.
- In PyTorch 1.1.0 and later, you should call them in the opposite order: `optimizer.step()` before `l
- Abp ajax The required antiforgery request token was not provided in either form field
- [LeetCode] 882. Reachable Nodes In Subdivided Graph 细分图中的可到达结点
- 1058 A+B in Hogwarts