2039.网络空闲的时刻.md

2039.网络空闲的时刻

/*
 * @lc app=leetcode.cn id=2039 lang=typescript
 *
 * [2039] 网络空闲的时刻
 */

// @lc code=start
function networkBecomesIdle(edges: number[][], patience: number[]): number {}
// @lc code=end

解法 1: BFS

function networkBecomesIdle(edges: number[][], patience: number[]): number {
  const n = patience.length
  const h: number[] = new Array(n).fill(-1),
    e: number[] = [],
    ne: number[] = []
  let idx = 0
  const add = (i: number, j: number) => {
    ;(e[idx] = j), (ne[idx] = h[i]), (h[i] = idx++)
  }
  for (let [u, v] of edges) {
    add(u, v)
    add(v, u)
  }
  const bfs = () => {
    const dist: number[] = new Array(n).fill(Infinity),
      st: number[] = []
    dist[0] = 0
    const queue = [0]
    for (let i of queue) {
      for (let k = h[i]; k !== -1; k = ne[k]) {
        const j = e[k]
        if (st[j]) continue
        st[j] = 1
        dist[j] = dist[i] + 1
        queue.push(j)
      }
    }
    return dist
  }
  const dist = bfs()
  let res = 0
  for (let i = 1; i < n; i++) {
    const last = Math.floor((dist[i] * 2 - 1) / patience[i]) * patience[i]
    res = Math.max(res, last + dist[i] * 2 + 1)
  }
  return res
}

Case

test.each([
  {
    input: {
      edges: [
        [0, 1],
        [1, 2],
      ],
      patience: [0, 2, 1],
    },
    output: 8,
  },
  {
    input: {
      edges: [
        [0, 1],
        [0, 2],
        [1, 2],
      ],
      patience: [0, 10, 10],
    },
    output: 3,
  },
])('input: edges = $input.edges, patience = $input.patience', ({ input: { edges, patience }, output }) => {
  expect(networkBecomesIdle(edges, patience)).toEqual(output)
})