3112. Minimum Time to Visit Disappearing Nodes

Posted on Edited on In

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:

1
2
3
4
5
6
7
8
9
10
11
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:

1
2
3
4
5
6
7
8
9
10
11
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:

1
2
3
4
5
6
7
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

Hints/Notes

  • dijkstra’s algorithm

Solution

Language: C++

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
    vector<vector<vector<int>>> graph;
    vector<int> res;
    priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;

    vector<int> minimumTime(int n, vector<vector<int>>& edges, vector<int>& disappear) {
        graph = vector<vector<vector<int>>>(n, vector<vector<int>>());
        buildGraph(edges);
        res = vector<int>(n, INT_MAX);
        pq.push({0, 0});
        while (!pq.empty() && n > 0) {
            auto edge = pq.top();
            pq.pop();
            int cur = edge[0];
            int v = edge[1];
            if (res[v] <= cur) {
                continue;
            }
            res[v] = cur;
            n--;
            cut(v, cur, disappear);
        }
        for (int i = 0; i < res.size(); i++) {
            if (res[i] == INT_MAX) {
                res[i] = -1;
            }
        }
        return res;
    }

    void buildGraph(vector<vector<int>>& edges) {
        for (auto edge : edges) {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            graph[u].push_back({v, w});
            graph[v].push_back({u, w});
        }
    }

    void cut(int u, int cur, vector<int>& disappear) {
        for (auto edge : graph[u]) {
            int v = edge[0];
            int w = edge[1];
            if (w + cur < disappear[v] && w + cur < res[v]) {
                pq.push({w + cur, v});
            }
        }
    }
};