Problem

There is an undirected graph of n nodes. You are given a 2D array edges, where edges[i] = [ui, vi, lengthi] describes an edge between node ui and node vi with a traversal time of lengthi units.

Additionally, you are given an array disappear, where disappear[i] denotes the time when the node i disappears from the graph and you won’t be able to visit it.

Note that the graph might be disconnected and might contain multiple edges.

Return the array answer, with answer[i] denoting the minimum units of time required to reach node i from node 0. If node i is unreachable from node 0 then answer[i] is -1.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


Input: n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,1,5]

Output: [0,-1,4]

Explanation:

![](https://assets.leetcode.com/uploads/2024/08/11/output-onlinepngtools.png)

We are starting our journey from node 0, and our goal is to find the minimum
time required to reach each node before it disappears.

  * For node 0, we don't need any time as it is our starting point.
  * For node 1, we need at least 2 units of time to traverse `edges[0]`. Unfortunately, it disappears at that moment, so we won't be able to visit it.
  * For node 2, we need at least 4 units of time to traverse `edges[2]`.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


Input: n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,3,5]

Output: [0,2,3]

Explanation:

![](https://assets.leetcode.com/uploads/2024/08/11/output-
onlinepngtools-1.png)

We are starting our journey from node 0, and our goal is to find the minimum
time required to reach each node before it disappears.

  * For node 0, we don't need any time as it is the starting point.
  * For node 1, we need at least 2 units of time to traverse `edges[0]`.
  * For node 2, we need at least 3 units of time to traverse `edges[0]` and `edges[1]`.

Example 3

1
2
3
4
5
6
7
8


Input: n = 2, edges = [[0,1,1]], disappear = [1,1]

Output: [0,-1]

Explanation:

Exactly when we reach node 1, it disappears.

Constraints

  • 1 <= n <= 5 * 10^4
  • 0 <= edges.length <= 10^5
  • edges[i] == [ui, vi, lengthi]
  • 0 <= ui, vi <= n - 1
  • 1 <= lengthi <= 10^5
  • disappear.length == n
  • 1 <= disappear[i] <= 10^5

Solution

Method 1 – Dijkstra’s Algorithm with Disappear Constraints

Intuition

We need to find the shortest time to each node, but can only visit a node before its disappear time. This is a classic shortest path problem with an extra constraint, so we use Dijkstra’s algorithm and skip nodes that disappear before we arrive.

Approach

  1. Build the undirected graph from the edges.
  2. Use a min-heap to process nodes by earliest arrival time.
  3. For each node, if arrival time is less than disappear time, update answer and continue to neighbors.
  4. If a node is unreachable or disappears before arrival, answer is -1.
  5. Return the answer array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <queue>
class Solution {
public:
    vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {
        vector<vector<pair<int,int>>> g(n);
        for (auto& e : edges) {
            g[e[0]].emplace_back(e[1], e[2]);
            g[e[1]].emplace_back(e[0], e[2]);
        }
        vector<int> ans(n, -1);
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
        pq.emplace(0, 0);
        while (!pq.empty()) {
            auto [t, u] = pq.top(); pq.pop();
            if (ans[u] != -1) continue;
            if (t >= disappear[u]) continue;
            ans[u] = t;
            for (auto& [v, w] : g[u]) {
                if (ans[v] == -1) pq.emplace(t + w, v);
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

func MinimumTime(n int, edges [][]int, disappear []int) []int {
    g := make([][][2]int, n)
    for _, e := range edges {
        g[e[0]] = append(g[e[0]], [2]int{e[1], e[2]})
        g[e[1]] = append(g[e[1]], [2]int{e[0], e[2]})
    }
    ans := make([]int, n)
    for i := range ans { ans[i] = -1 }
    pq := &heapPair{}
    heap.Init(pq)
    heap.Push(pq, pair{0, 0})
    for pq.Len() > 0 {
        p := heap.Pop(pq).(pair)
        if ans[p.u] != -1 || p.d >= disappear[p.u] { continue }
        ans[p.u] = p.d
        for _, e := range g[p.u] {
            v, w := e[0], e[1]
            if ans[v] == -1 {
                heap.Push(pq, pair{p.d + w, v})
            }
        }
    }
    return ans
}
type pair struct{ d, u int }
type heapPair []pair
func (h heapPair) Len() int { return len(h) }
func (h heapPair) Less(i, j int) bool { return h[i].d < h[j].d }
func (h heapPair) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *heapPair) Push(x interface{}) { *h = append(*h, x.(pair)) }
func (h *heapPair) Pop() interface{} { old := *h; x := old[len(old)-1]; *h = old[:len(old)-1]; return x }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    public int[] minimumTime(int n, int[][] edges, int[] disappear) {
        List<int[]>[] g = new List[n];
        for (int i = 0; i < n; i++) g[i] = new ArrayList<>();
        for (int[] e : edges) {
            g[e[0]].add(new int[]{e[1], e[2]});
            g[e[1]].add(new int[]{e[0], e[2]});
        }
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{0, 0});
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int t = cur[0], u = cur[1];
            if (ans[u] != -1 || t >= disappear[u]) continue;
            ans[u] = t;
            for (int[] e : g[u]) {
                int v = e[0], w = e[1];
                if (ans[v] == -1) pq.offer(new int[]{t + w, v});
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun minimumTime(n: Int, edges: Array<IntArray>, disappear: IntArray): IntArray {
        val g = Array(n) { mutableListOf<Pair<Int, Int>>() }
        for (e in edges) {
            g[e[0]].add(e[1] to e[2])
            g[e[1]].add(e[0] to e[2])
        }
        val ans = IntArray(n) { -1 }
        val pq = PriorityQueue<Pair<Int, Int>>(compareBy { it.first })
        pq.add(0 to 0)
        while (pq.isNotEmpty()) {
            val (t, u) = pq.poll()
            if (ans[u] != -1 || t >= disappear[u]) continue
            ans[u] = t
            for ((v, w) in g[u]) {
                if (ans[v] == -1) pq.add(t + w to v)
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

from typing import List
import heapq
class Solution:
    def minimumTime(self, n: int, edges: List[List[int]], disappear: List[int]) -> List[int]:
        g = [[] for _ in range(n)]
        for u, v, w in edges:
            g[u].append((v, w))
            g[v].append((u, w))
        ans = [-1] * n
        heap = [(0, 0)]
        while heap:
            t, u = heapq.heappop(heap)
            if ans[u] != -1 or t >= disappear[u]:
                continue
            ans[u] = t
            for v, w in g[u]:
                if ans[v] == -1:
                    heapq.heappush(heap, (t + w, v))
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

use std::collections::BinaryHeap;
use std::cmp::Reverse;
impl Solution {
    pub fn minimum_time(n: i32, edges: Vec<Vec<i32>>, disappear: Vec<i32>) -> Vec<i32> {
        let n = n as usize;
        let mut g = vec![vec![]; n];
        for e in &edges {
            g[e[0] as usize].push((e[1] as usize, e[2]));
            g[e[1] as usize].push((e[0] as usize, e[2]));
        }
        let mut ans = vec![-1; n];
        let mut heap = BinaryHeap::new();
        heap.push(Reverse((0, 0)));
        while let Some(Reverse((t, u))) = heap.pop() {
            if ans[u] != -1 || t >= disappear[u] { continue; }
            ans[u] = t;
            for &(v, w) in &g[u] {
                if ans[v] == -1 {
                    heap.push(Reverse((t + w, v)));
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    minimumTime(n: number, edges: number[][], disappear: number[]): number[] {
        const g: number[][][] = Array.from({length: n}, () => []);
        for (const [u, v, w] of edges) {
            g[u].push([v, w]);
            g[v].push([u, w]);
        }
        const ans = Array(n).fill(-1);
        const heap: [number, number][] = [[0, 0]];
        while (heap.length) {
            heap.sort((a, b) => a[0] - b[0]);
            const [t, u] = heap.shift()!;
            if (ans[u] !== -1 || t >= disappear[u]) continue;
            ans[u] = t;
            for (const [v, w] of g[u]) {
                if (ans[v] === -1) heap.push([t + w, v]);
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O((n + m) log n) — Dijkstra’s algorithm with a heap for all nodes and edges.
  • 🧺 Space complexity: O(n + m) — For graph storage and heap.