# 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:

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.

``````class Solution {
public:
int reachableNodes(vector<vector<int>>& edges, int M, int N) {
int res = 0;
vector<vector<int>> graph(N, vector<int>(N, -1));
vector<bool> visited(N);
priority_queue<pair<int, int>> pq;
pq.push({M, 0});
for (auto &edge : edges) {
graph[edge[0]][edge[1]] = edge[2];
graph[edge[1]][edge[0]] = edge[2];
}
while (!pq.empty()) {
auto t= pq.top(); pq.pop();
int move = t.first, cur = t.second;
if (visited[cur]) continue;
visited[cur] = true;
++res;
for (int i = 0; i < N; ++i) {
if (graph[cur][i] == -1) continue;
if (move > graph[cur][i] && !visited[i]) {
pq.push({move - graph[cur][i] - 1, i});
}
graph[i][cur] -= min(move, graph[cur][i]);
res += min(move, graph[cur][i]);
}
}
return res;
}
};
``````

``````class Solution {
public:
int reachableNodes(vector<vector<int>>& edges, int M, int N) {
int res = 0;
unordered_map<int, unordered_map<int, int>> graph;
vector<bool> visited(N);
priority_queue<pair<int, int>> pq;
pq.push({M, 0});
for (auto &edge : edges) {
graph[edge[0]][edge[1]] = edge[2];
graph[edge[1]][edge[0]] = edge[2];
}
while (!pq.empty()) {
auto t= pq.top(); pq.pop();
int move = t.first, cur = t.second;
if (visited[cur]) continue;
visited[cur] = true;
++res;
for (auto &a : graph[cur]) {
if (move > a.second && !visited[a.first]) {
pq.push({move - a.second - 1, a.first});
}
graph[a.first][cur] -= min(move, a.second);
res += min(move, a.second);
}
}
return res;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/882

https://leetcode.com/problems/reachable-nodes-in-subdivided-graph/

https://leetcode.com/problems/reachable-nodes-in-subdivided-graph/discuss/156777/Java-Dijkstra-Solution

https://leetcode.com/problems/reachable-nodes-in-subdivided-graph/discuss/156739/C%2B%2BJavaPython-Dijkstra-%2B-Priority-Queue

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation