Sponsored
Sponsored
We treat the problem as a shortest path problem. Each edge between nodes in the original graph may be subdivided logically without explicitly constructing all new nodes. We can utilize Dijkstra's algorithm to calculate the shortest paths starting from node 0, considering edge subdivisions.
Time Complexity: O(E + V log V), where E is the number of edges and V the number of vertices.
Space Complexity: O(E + V) for storing the graph and distances.
1import heapq
2
3def reachableNodes(edges, maxMoves, n):
4 graph = {i: {} for i in range(n)}
5 for u, v, cnt in edges:
6 graph[u][v] = cnt
7 graph[v][u] = cnt
8 pq = [(0, 0)]
9 dist = {0: 0}
10 result = 0
11 used_edges = {}
12 while pq:
13 curr_dist, u = heapq.heappop(pq)
14 if curr_dist > dist.get(u, float('inf')):
15 continue
16 result += 1
17 for v, cnt in graph[u].items():
18 v_dist = curr_dist + cnt + 1
19 if v_dist <= maxMoves and v_dist < dist.get(v, float('inf')):
20 dist[v] = v_dist
21 heapq.heappush(pq, (v_dist, v))
22 used_edges[(u, v)] = min(cnt, maxMoves - curr_dist)
23 return result + sum(min(v1+v2, cnt) for (u, v), cnt in graph.items() for v1, v2 in [(used_edges.get((u, v), 0), used_edges.get((v, u), 0))])
24
25# Example usage
26# edges = [[0,1,10],[0,2,1],[1,2,2]]
27# maxMoves = 6
28# n = 3
29# print(reachableNodes(edges, maxMoves, n)) # Output: 13The function initializes a graph where each node points to a dictionary of its connected nodes treating cnt as weights for route expansion. This is reminiscent of representing weighted edges for pathfinding algorithms. We use a priority queue to maintain node distances akin to Dijkstra's algorithm, continually exploring until all reachable nodes are calculated within maxMoves.
Instead of explicitly constructing the whole subdivided graph, we utilize a DFS strategy. By expanding paths logically through recursion and considering move limits, we can calculate the number of reachable nodes without extra space overhead.
Time Complexity: O(V + E), where V is the number of vertices and E the number of edges, as it involves visiting nodes and edges logically.
Space Complexity: O(V + E) for adjacency list and visited set.
1def reachableNodesDFS(edges, maxMoves, n):
2 graph = {i:
This approach involves using Dijkstra's algorithm to calculate the shortest distance from node 0 to all other nodes in the subdivided graph. The subdivision requires splitting each edge into a path with additional nodes. The priority queue maintains nodes sorted by distance, ensuring efficient processing of the shortest paths first.
Time Complexity: O(E + N log N), where E is the number of edges and N is the number of nodes due to priority queue operations.
Space Complexity: O(N + E), for storing graph, distance, and used nodes mappings.
1#include <iostream>
2#include <vector>
3#include <queue>
#include <unordered_map>
#include <climits>
using namespace std;
int reachableNodes(vector<vector<int>>& edges, int maxMoves, int n) {
vector<unordered_map<int, int>> graph(n);
for (auto &edge : edges) {
int u = edge[0], v = edge[1], cnt = edge[2];
graph[u][v] = cnt;
graph[v][u] = cnt;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, 0});
vector<int> dist(n, INT_MAX);
dist[0] = 0;
unordered_map<int, int> used;
int res = 0;
while (!pq.empty()) {
auto [d, node] = pq.top(); pq.pop();
if (d > dist[node]) continue;
res++;
for (auto &[neighbor, cnt] : graph[node]) {
int v = min(cnt, maxMoves - d);
used[node * n + neighbor] = v;
int d2 = d + cnt + 1;
if (d2 < dist[neighbor]) {
dist[neighbor] = d2;
pq.push({d2, neighbor});
}
}
}
for (auto &edge : edges) {
int u = edge[0], v = edge[1], cnt = edge[2];
res += min(cnt, (used[u * n + v]) + (used[v * n + u]));
}
return res;
}
// Example usage:
// int main() {
// vector<vector<int>> edges = {{0,1,10},{0,2,1},{1,2,2}};
// int maxMoves = 6, n = 3;
// cout << reachableNodes(edges, maxMoves, n) << endl; // Output: 13
// return 0;
// }This approach employs BFS to explore the graph iteratively. Unlike Dijkstra, BFS is less concerned with path cost optimization and focuses on level-wise expansion. It's useful when all edge weights are equal. Here, edges must be handled considering additional costs per neighbor negotiation based on subdivided portions of the graph.
Time Complexity: O(E + N^2), due to BFS and operations at each node with the distance array update.
Space Complexity: O(N + E), capturing the adjacency list and additional structures like queue and distance array.
1import java.util.*;
2
This solution builds an adjacency list to represent the graph. It applies a DFS approach, where each node recursively attempts to visit connected nodes, tracking nodes reached using a set. Subdivisions are not created explicitly, and instead, logical path expansion is calculated by allowable traversal of each edge within given maxMoves.
This C++ code uses a priority queue (min-heap) and a custom comparator to implement Dijkstra's algorithm. Nodes are stored with their distances. The graph is constructed with adjacency lists. The main loop finds the current closest node, examines all neighbors, and when a shorter path is found, it's updated. The 'used' map tracks how many nodes we can use on each subdivided edge.
The Java solution explores combinations of reachable nodes using BFS. A queue is used to maintain exploration from the starting node iteratively. Each node's reachable distance is updated if a shorter path via a neighbor is discovered, counting reachable nodes based on the accumulated distance.