Welcome to Subscribe On Youtube

3112. Minimum Time to Visit Disappearing Nodes

Description

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.

Notice 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.

 

Example 1:

<img 10px="" alt="" padding:="" src="https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/3100-3199/3112.Minimum%20Time%20to%20Visit%20Disappearing%20Nodes/images/example1.png" style="width: 350px; height: 210px;" />

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

Output: [0,-1,4]

Explanation:

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:

<img 10px="" alt="" padding:="" src="https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/3100-3199/3112.Minimum%20Time%20to%20Visit%20Disappearing%20Nodes/images/example2.png" style="width: 350px; height: 210px;" />

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

Output: [0,2,3]

Explanation:

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:

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 * 104
  • 0 <= edges.length <= 105
  • edges[i] == [ui, vi, lengthi]
  • 0 <= ui, vi <= n - 1
  • 1 <= lengthi <= 105
  • disappear.length == n
  • 1 <= disappear[i] <= 105

Solutions

Solution 1: Heap Optimized Dijkstra

First, we create an adjacency list $g$ to store the edges of the graph. Then we create an array $dist$ to store the shortest distance from node $0$ to other nodes. We initialize $dist[0] = 0$ and the distance of other nodes is initialized to infinity.

Then, we use Dijkstra’s algorithm to calculate the shortest distance from node $0$ to other nodes. The specific steps are as follows:

  1. Create a priority queue $q$ to store the distance and node number of nodes. Initially, add node $0$ to the queue with a distance of $0$.
  2. Take out a node $u$ from the queue. If the distance $du$ of $u$ is greater than $dist[u]$, it means that $u$ has been updated, so skip it directly.
  3. Traverse all neighbor nodes $v$ of node $u$. If $dist[v] > dist[u] + w$ and $dist[u] + w < disappear[v]$, then update $dist[v] = dist[u] + w$ and add node $v$ to the queue.
  4. Repeat steps 2 and 3 until the queue is empty.

Finally, we traverse the $dist$ array. If $dist[i] < disappear[i]$, then $answer[i] = dist[i]$, otherwise $answer[i] = -1$.

The time complexity is $O(m \times \log m)$, and the space complexity is $O(m)$, where $m$ is the number of edges.

  • class Solution {
        public int[] minimumTime(int n, int[][] edges, int[] disappear) {
            List<int[]>[] g = new List[n];
            Arrays.setAll(g, k -> new ArrayList<>());
            for (var e : edges) {
                int u = e[0], v = e[1], w = e[2];
                g[u].add(new int[] {v, w});
                g[v].add(new int[] {u, w});
            }
            int[] dist = new int[n];
            Arrays.fill(dist, 1 << 30);
            dist[0] = 0;
            PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
            pq.offer(new int[] {0, 0});
            while (!pq.isEmpty()) {
                var e = pq.poll();
                int du = e[0], u = e[1];
                if (du > dist[u]) {
                    continue;
                }
                for (var nxt : g[u]) {
                    int v = nxt[0], w = nxt[1];
                    if (dist[v] > dist[u] + w && dist[u] + w < disappear[v]) {
                        dist[v] = dist[u] + w;
                        pq.offer(new int[] {dist[v], v});
                    }
                }
            }
            int[] ans = new int[n];
            for (int i = 0; i < n; ++i) {
                ans[i] = dist[i] < disappear[i] ? dist[i] : -1;
            }
            return ans;
        }
    }
    
  • class Solution {
    public:
        vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {
            vector<vector<pair<int, int>>> g(n);
            for (const auto& e : edges) {
                int u = e[0], v = e[1], w = e[2];
                g[u].push_back({v, w});
                g[v].push_back({u, w});
            }
    
            vector<int> dist(n, 1 << 30);
            dist[0] = 0;
    
            using pii = pair<int, int>;
            priority_queue<pii, vector<pii>, greater<pii>> pq;
            pq.push({0, 0});
    
            while (!pq.empty()) {
                auto [du, u] = pq.top();
                pq.pop();
    
                if (du > dist[u]) {
                    continue;
                }
    
                for (auto [v, w] : g[u]) {
                    if (dist[v] > dist[u] + w && dist[u] + w < disappear[v]) {
                        dist[v] = dist[u] + w;
                        pq.push({dist[v], v});
                    }
                }
            }
    
            vector<int> ans(n);
            for (int i = 0; i < n; ++i) {
                ans[i] = dist[i] < disappear[i] ? dist[i] : -1;
            }
    
            return ans;
        }
    };
    
  • class Solution:
        def minimumTime(
            self, n: int, edges: List[List[int]], disappear: List[int]
        ) -> List[int]:
            g = defaultdict(list)
            for u, v, w in edges:
                g[u].append((v, w))
                g[v].append((u, w))
            dist = [inf] * n
            dist[0] = 0
            q = [(0, 0)]
            while q:
                du, u = heappop(q)
                if du > dist[u]:
                    continue
                for v, w in g[u]:
                    if dist[v] > dist[u] + w and dist[u] + w < disappear[v]:
                        dist[v] = dist[u] + w
                        heappush(q, (dist[v], v))
            return [a if a < b else -1 for a, b in zip(dist, disappear)]
    
    
  • func minimumTime(n int, edges [][]int, disappear []int) []int {
    	g := make([][]pair, n)
    	for _, e := range edges {
    		u, v, w := e[0], e[1], e[2]
    		g[u] = append(g[u], pair{v, w})
    		g[v] = append(g[v], pair{u, w})
    	}
    
    	dist := make([]int, n)
    	for i := range dist {
    		dist[i] = 1 << 30
    	}
    	dist[0] = 0
    
    	pq := hp{ {0, 0} }
    
    	for len(pq) > 0 {
    		du, u := pq[0].dis, pq[0].u
    		heap.Pop(&pq)
    
    		if du > dist[u] {
    			continue
    		}
    
    		for _, nxt := range g[u] {
    			v, w := nxt.dis, nxt.u
    			if dist[v] > dist[u]+w && dist[u]+w < disappear[v] {
    				dist[v] = dist[u] + w
    				heap.Push(&pq, pair{dist[v], v})
    			}
    		}
    	}
    
    	ans := make([]int, n)
    	for i := 0; i < n; i++ {
    		if dist[i] < disappear[i] {
    			ans[i] = dist[i]
    		} else {
    			ans[i] = -1
    		}
    	}
    
    	return ans
    }
    
    type pair struct{ dis, u int }
    type hp []pair
    
    func (h hp) Len() int           { return len(h) }
    func (h hp) Less(i, j int) bool { return h[i].dis < h[j].dis }
    func (h hp) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
    func (h *hp) Push(v any)        { *h = append(*h, v.(pair)) }
    func (h *hp) Pop() any          { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
    
  • function minimumTime(n: number, edges: number[][], disappear: number[]): number[] {
        const g: [number, number][][] = Array.from({ length: n }, () => []);
        for (const [u, v, w] of edges) {
            g[u].push([v, w]);
            g[v].push([u, w]);
        }
        const dist = Array.from({ length: n }, () => Infinity);
        dist[0] = 0;
        const pq = new PriorityQueue({
            compare: (a, b) => (a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]),
        });
        pq.enqueue([0, 0]);
        while (pq.size() > 0) {
            const [du, u] = pq.dequeue()!;
            if (du > dist[u]) {
                continue;
            }
            for (const [v, w] of g[u]) {
                if (dist[v] > dist[u] + w && dist[u] + w < disappear[v]) {
                    dist[v] = dist[u] + w;
                    pq.enqueue([dist[v], v]);
                }
            }
        }
        return dist.map((a, i) => (a < disappear[i] ? a : -1));
    }
    
    

All Problems

All Solutions