跳转至

3112. 访问消失节点的最少时间

题目描述

给你一个二维数组 edges 表示一个 n 个点的无向图，其中 edges[i] = [ui, vi, lengthi] 表示节点 ui 和节点 vi 之间有一条需要 lengthi 单位时间通过的无向边。

同时给你一个数组 disappear ，其中 disappear[i] 表示节点 i 从图中消失的时间点，在那一刻及以后，你无法再访问这个节点。

注意，图有可能一开始是不连通的，两个节点之间也可能有多条边。

请你返回数组 answer ，answer[i] 表示从节点 0 到节点 i 需要的 最少 单位时间。如果从节点 0 出发 无法 到达节点 i ，那么 answer[i] 为 -1 。

 

示例 1：

输入：n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,1,5]

输出：[0,-1,4]

解释：

我们从节点 0 出发，目的是用最少的时间在其他节点消失之前到达它们。

  • 对于节点 0 ，我们不需要任何时间，因为它就是我们的起点。
  • 对于节点 1 ，我们需要至少 2 单位时间，通过 edges[0] 到达。但当我们到达的时候，它已经消失了，所以我们无法到达它。
  • 对于节点 2 ，我们需要至少 4 单位时间，通过 edges[2] 到达。

示例 2：

输入：n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,3,5]

输出：[0,2,3]

解释：

我们从节点 0 出发，目的是用最少的时间在其他节点消失之前到达它们。

  • 对于节点 0 ，我们不需要任何时间，因为它就是我们的起点。
  • 对于节点 1 ，我们需要至少 2 单位时间，通过 edges[0] 到达。
  • 对于节点 2 ，我们需要至少 3 单位时间，通过 edges[0] 和 edges[1] 到达。

示例 3：

输入：n = 2, edges = [[0,1,1]], disappear = [1,1]

输出：[0,-1]

解释：

当我们到达节点 1 的时候，它恰好消失，所以我们无法到达节点 1 。

 

提示：

  • 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

解法

方法一：堆优化的 Dijkstra

我们先创建一个邻接表 $\textit{g}$，用于存储图的边。然后创建一个数组 $\textit{dist}$，用于存储从节点 $0$ 到其他节点的最短距离。初始化 $\textit{dist}[0] = 0$，其余节点的距离初始化为无穷大。

然后，我们使用 Dijkstra 算法计算从节点 $0$ 到其他节点的最短距离。具体步骤如下：

  1. 创建一个优先队列 $\textit{pq}$，用于存储节点的距离和节点编号，初始时将节点 $0$ 加入队列，距离为 $0$。
  2. 从队列中取出一个节点 $u$，如果 $u$ 的距离 $du$ 大于 $\textit{dist}[u]$，说明 $u$ 已经被更新过了，直接跳过。
  3. 遍历节点 $u$ 的所有邻居节点 $v$，如果 $\textit{dist}[v] > \textit{dist}[u] + w$ 且 $\textit{dist}[u] + w < \textit{disappear}[v]$，则更新 $\textit{dist}[v] = \textit{dist}[u] + w$，并将节点 $v$ 加入队列。
  4. 重复步骤 2 和步骤 3，直到队列为空。

最后，我们遍历 $\textit{dist}$ 数组，如果 $\textit{dist}[i] < \textit{disappear}[i]$，则 $\textit{answer}[i] = \textit{dist}[i]$，否则 $\textit{answer}[i] = -1$。

时间复杂度 $O(m \times \log m)$，空间复杂度 $O(m)$。其中 $m$ 是边的数量。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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
        pq = [(0, 0)]
        while pq:
            du, u = heappop(pq)
            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(pq, (dist[v], v))
        return [a if a < b else -1 for a, b in zip(dist, disappear)]

 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
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;
    }
}

 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
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;
    }
};

 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
52
53
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 }

 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
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));
}

评论