列表

详情

2039. 网络空闲的时刻

给你一个有 n 个服务器的计算机网络，服务器编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示服务器 ui 和 vi 之间有一条信息线路，在 一秒 内它们之间可以传输 任意 数目的信息。再给你一个长度为 n 且下标从 0 开始的整数数组 patience 。

题目保证所有服务器都是 相通 的，也就是说一个信息从任意服务器出发，都可以通过这些信息线路直接或间接地到达任何其他服务器。

编号为 0 的服务器是 主 服务器，其他服务器为 数据 服务器。每个数据服务器都要向主服务器发送信息，并等待回复。信息在服务器之间按 最优 线路传输，也就是说每个信息都会以 最少时间 到达主服务器。主服务器会处理 所有 新到达的信息并 立即 按照每条信息来时的路线 反方向 发送回复信息。

在 0 秒的开始，所有数据服务器都会发送各自需要处理的信息。从第 1 秒开始，每 一秒最 开始 时，每个数据服务器都会检查它是否收到了主服务器的回复信息（包括新发出信息的回复信息）：

当没有任何信息在线路上传输或者到达某服务器时，该计算机网络变为 空闲 状态。

请返回计算机网络变为 空闲 状态的 最早秒数 。

 

示例 1：

example 1

输入：edges = [[0,1],[1,2]], patience = [0,2,1]
输出：8
解释：
0 秒最开始时，
- 数据服务器 1 给主服务器发出信息（用 1A 表示）。
- 数据服务器 2 给主服务器发出信息（用 2A 表示）。

1 秒时，
- 信息 1A 到达主服务器，主服务器立刻处理信息 1A 并发出 1A 的回复信息。
- 数据服务器 1 还没收到任何回复。距离上次发出信息过去了 1 秒（1 < patience[1] = 2），所以不会重发信息。
- 数据服务器 2 还没收到任何回复。距离上次发出信息过去了 1 秒（1 == patience[2] = 1），所以它重发一条信息（用 2B 表示）。

2 秒时，
- 回复信息 1A 到达服务器 1 ，服务器 1 不会再重发信息。
- 信息 2A 到达主服务器，主服务器立刻处理信息 2A 并发出 2A 的回复信息。
- 服务器 2 重发一条信息（用 2C 表示）。
...
4 秒时，
- 回复信息 2A 到达服务器 2 ，服务器 2 不会再重发信息。
...
7 秒时，回复信息 2D 到达服务器 2 。

从第 8 秒开始，不再有任何信息在服务器之间传输，也不再有信息到达服务器。
所以第 8 秒是网络变空闲的最早时刻。

示例 2：

example 2

输入：edges = [[0,1],[0,2],[1,2]], patience = [0,10,10]
输出：3
解释：数据服务器 1 和 2 第 2 秒初收到回复信息。
从第 3 秒开始，网络变空闲。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int networkBecomesIdle(vector<vector<int>>& edges, vector<int>& patience) { } };

golang 解法, 执行用时: 404 ms, 内存消耗: 33.6 MB, 提交时间: 2022-12-09 15:59:09 

func networkBecomesIdle(edges [][]int, patience []int) (ans int) {
    n, graph := len(patience), map[int][]int{}
    for _, edge := range edges {
        graph[edge[0]] = append(graph[edge[0]], edge[1])
        graph[edge[1]] = append(graph[edge[1]], edge[0])
    }
    distance, queue := make([]int, n), [][]int{{0, 0}}
    distance[0] = -1
    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]
        for _, other := range graph[cur[0]] {
            if distance[other] == 0 {
                distance[other] = cur[1] + 1
                queue = append(queue, []int{other, cur[1] + 1})
            }
        }
    }
    for i := 1; i < n; i++ {
        d, p := distance[i] * 2, patience[i]
        ans = max(ans, (d - 1) / p * p + d + 1)
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

javascript 解法, 执行用时: 464 ms, 内存消耗: 100.7 MB, 提交时间: 2022-12-09 15:58:45 

/**
 * @param {number[][]} edges
 * @param {number[]} patience
 * @return {number}
 */
var networkBecomesIdle = function(edges, patience) {
    const n = patience.length, graph = new Map()
    for(const edge of edges) {
        var l1, l2
        if(graph.has(edge[0]))
            l1 = graph.get(edge[0])
        else
            l1 = new Array()
        l1.push(edge[1])
        graph.set(edge[0], l1)
        if(graph.has(edge[1]))
            l2 = graph.get(edge[1])
        else
            l2 = new Array()
        l2.push(edge[0])
        graph.set(edge[1], l2)
    }
    const distance = new Array(n).fill(Number.MAX_SAFE_INTEGER)
    distance[0] = 0
    let queue = [0], cost = 0
    while(queue.length > 0) {
        cost += 1
        next = new Array()
        for(const server of queue)
            for(const other of graph.get(server))
                if(distance[other] == Number.MAX_SAFE_INTEGER) {
                    distance[other] = cost
                    next.push(other)
                }
        queue = next
    }
    let ans = 0
    for(let i = 1; i < n; i++) {
        const d = distance[i] * 2, p = patience[i]
        ans = Math.max(ans, Math.floor((d - 1) / p) * p + d)
    }
    return ans + 1
};

python3 解法, 执行用时: 560 ms, 内存消耗: 54.9 MB, 提交时间: 2022-12-09 15:58:30 

class Solution:
    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:
        n = len(patience)
        distance = [inf] * n
        graph = defaultdict(list)
        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)
        queue = deque([(0, 0)])
        distance[0] = 0
        while queue:
            server, cost = queue.popleft()
            distance[server] = cost
            for other in graph[server]:
                if distance[other] == inf:
                    distance[other] = cost + 1
                    queue.append((other, cost + 1))
        ans = 0
        for i in range(n):
            d, p = distance[i] * 2, patience[i]
            ans = max(ans, (d - 1) // p * p + d if p else 0)
        return ans + 1

golang 解法, 执行用时: 320 ms, 内存消耗: 26 MB, 提交时间: 2022-12-09 15:58:09 

func networkBecomesIdle(edges [][]int, patience []int) (ans int) {
    n := len(patience)
    g := make([][]int, n)
    for _, e := range edges {
        x, y := e[0], e[1]
        g[x] = append(g[x], y)
        g[y] = append(g[y], x)
    }

    vis := make([]bool, n)
    vis[0] = true
    q := []int{0}
    for dist := 1; q != nil; dist++ {
        tmp := q
        q = nil
        for _, x := range tmp {
            for _, v := range g[x] {
                if vis[v] {
                    continue
                }
                vis[v] = true
                q = append(q, v)
                ans = max(ans, (dist*2-1)/patience[v]*patience[v]+dist*2+1)
            }
        }
    }
    return
}

func max(a, b int) int {
    if b > a {
        return b
    }
    return a
}

java 解法, 执行用时: 67 ms, 内存消耗: 91.2 MB, 提交时间: 2022-12-09 15:57:54 

class Solution {
    public int networkBecomesIdle(int[][] edges, int[] patience) {
        int n = patience.length;       
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; ++i) {
            adj[i] = new ArrayList<Integer>();
        }
        boolean[] visit = new boolean[n];
        for (int[] v : edges) {
            adj[v[0]].add(v[1]);
            adj[v[1]].add(v[0]);
        }

        Queue<Integer> queue = new ArrayDeque<Integer>();
        queue.offer(0);
        visit[0] = true;
        int dist = 1;
        int ans = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curr = queue.poll();
                for (int v : adj[curr]) {
                    if (visit[v]) {
                        continue;
                    }
                    queue.offer(v);
                    int time = patience[v] * ((2 * dist - 1) / patience[v]) + 2 * dist + 1;
                    ans = Math.max(ans, time);
                    visit[v] = true;
                }
            }
            dist++;
        }
        return ans;
    }
}

python3 解法, 执行用时: 516 ms, 内存消耗: 45.9 MB, 提交时间: 2022-12-09 15:57:43 

class Solution:
    def networkBecomesIdle(self, edges: List[List[int]], patience: List[int]) -> int:
        n = len(patience)
        g = [[] for _ in range(n)]
        for u, v in edges:
            g[u].append(v)
            g[v].append(u)

        vis = [False] * n
        vis[0] = True
        q = deque([0])
        ans, dist = 0, 1
        while q:
            for _ in range(len(q)):
                u = q.popleft()
                for v in g[u]:
                    if vis[v]:
                        continue
                    vis[v] = True
                    q.append(v)
                    ans = max(ans, (dist * 2 - 1) // patience[v] * patience[v] + dist * 2 + 1)
            dist += 1
        return ans

上一题

© 2024 leetcode.cn