Minimum Time to Visit Disappearing Nodes
Problem
There is an undirected graph of n nodes. edges[i] = [u, v, w] means there is an edge between u and v that takes w units of time to travel. You also have an array disappear where node i disappears at time disappear[i] and cannot be visited at or after that time. Starting from node 0 at time 0, return an array answer where answer[i] is the minimum time to reach node i, or -1 if it is unreachable in time.
This is Dijkstra's shortest path with one extra rule during relaxation: an arrival at node v at time t only counts if t < disappear[v]. Any later arrival is forbidden, so we never push it onto the heap.
n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,1,5][0, -1, 4]import heapq
def minimum_time(n, edges, disappear):
adj = {i: [] for i in range(n)}
for u, v, w in edges:
adj[u].append((v, w))
adj[v].append((u, w))
dist = [float('inf')] * n
dist[0] = 0
pq = [(0, 0)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, w in adj[u]:
nd = d + w
if nd < disappear[v] and nd < dist[v]:
dist[v] = nd
heapq.heappush(pq, (nd, v))
return [-1 if dist[i] == float('inf') else dist[i] for i in range(n)]function minimumTime(n, edges, disappear) {
const adj = Array.from({ length: n }, () => []);
for (const [u, v, w] of edges) {
adj[u].push([v, w]);
adj[v].push([u, w]);
}
const dist = new Array(n).fill(Infinity);
dist[0] = 0;
const pq = [[0, 0]];
while (pq.length) {
pq.sort((a, b) => a[0] - b[0]);
const [d, u] = pq.shift();
if (d > dist[u]) continue;
for (const [v, w] of adj[u]) {
const nd = d + w;
if (nd < disappear[v] && nd < dist[v]) {
dist[v] = nd;
pq.push([nd, v]);
}
}
}
return dist.map((x) => (x === Infinity ? -1 : x));
}class Solution {
public int[] minimumTime(int n, int[][] edges, int[] disappear) {
List<int[]>[] adj = new List[n];
for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
for (int[] e : edges) {
adj[e[0]].add(new int[]{e[1], e[2]});
adj[e[1]].add(new int[]{e[0], e[2]});
}
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[0] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{0, 0});
while (!pq.isEmpty()) {
int[] top = pq.poll();
int d = top[0], u = top[1];
if (d > dist[u]) continue;
for (int[] nb : adj[u]) {
int v = nb[0], nd = d + nb[1];
if (nd < disappear[v] && nd < dist[v]) {
dist[v] = nd;
pq.offer(new int[]{nd, v});
}
}
}
int[] ans = new int[n];
for (int i = 0; i < n; i++) ans[i] = dist[i] == Integer.MAX_VALUE ? -1 : dist[i];
return ans;
}
}class Solution {
public:
vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {
vector<vector<pair<int,int>>> adj(n);
for (auto& e : edges) {
adj[e[0]].push_back({e[1], e[2]});
adj[e[1]].push_back({e[0], e[2]});
}
vector<long long> dist(n, LLONG_MAX);
dist[0] = 0;
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
pq.push({0, 0});
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;
for (auto& [v, w] : adj[u]) {
long long nd = d + w;
if (nd < disappear[v] && nd < dist[v]) {
dist[v] = nd;
pq.push({nd, v});
}
}
}
vector<int> ans(n);
for (int i = 0; i < n; i++) ans[i] = dist[i] == LLONG_MAX ? -1 : (int) dist[i];
return ans;
}
};Explanation
Reaching a node "in time" means arriving strictly before it vanishes. Since edge times are non-negative, the earliest possible arrival at each node is its shortest-path distance from node 0 — so the backbone is plain Dijkstra.
We keep a dist array (everything infinite except dist[0] = 0) and a min-heap of (time, node). We always expand the smallest-time entry, which guarantees that when we settle a node its time is truly minimal.
The only twist is in relaxation. Normally we accept an edge if it improves the distance; here we add a second condition: the new arrival time nd = d + w must also satisfy nd < disappear[v]. If the node would already be gone, we discard that route entirely and never push it.
At the end, any node still at infinity could not be reached before disappearing, so its answer is -1; otherwise it is the settled distance.
Worked example: from node 0, node 1 needs time 2 but disappear[1] = 1, so that relaxation is rejected and node 1 stays -1. Node 2 is reached at time 4 < 5, giving the answer [0, -1, 4].