2045.到达目的地的第二短时间.md

2045.到达目的地的第二短时间

/*
 * @lc app=leetcode.cn id=2045 lang=typescript
 *
 * [2045] 到达目的地的第二短时间
 */

// @lc code=start
function secondMinimum(n: number, edges: number[][], time: number, change: number): number {}
// @lc code=end

解法 1: 使用优先队列

function secondMinimum(n: number, edges: number[][], time: number, change: number): number {
  const next = new Map<number, Set<number>>()
  for (const [from, to] of edges) {
    if (!next.has(from)) {
      next.set(from, new Set<number>())
    }
    if (!next.has(to)) {
      next.set(to, new Set<number>())
    }
    next.get(from)!.add(to)
    next.get(to)!.add(from)
  }

  const heap = new Heap<{ city: number; timeSum: number }>((a, b) => {
    return a.timeSum < b.timeSum
  })
  const visit = new Array(n + 1).fill(0).map(() => [0, 0])
  heap.push({ city: 1, timeSum: 0 })
  let flag = false
  while (heap.size() > 0) {
    const { city, timeSum } = heap.pop()!
    if (city === n) {
      if (flag) return timeSum
      flag = true
    }

    for (const to of next.get(city)!) {
      let t = timeSum
      if (Math.floor(t / change) % 2 === 1) {
        t = (Math.floor(t / change) + 1) * change
      }
      t += time

      if (visit[to][0] < 2 && visit[to][1] < t) {
        heap.push({ city: to, timeSum: t })
        visit[to][0]++
        visit[to][1] = t
      }
    }
  }
  return -1
}
class Heap<T> {
  private _heap: T[] = []
  constructor(private _comparator: (n1: T, n2: T) => boolean) {}
  private swap(i: number, j: number) {
    ;[this._heap[i], this._heap[j]] = [this._heap[j], this._heap[i]]
  }
  private _has(i: number) {
    return Object.prototype.hasOwnProperty.call(this._heap, i)
  }
  private comparator(i: number, j: number) {
    return this._comparator(this._heap[i], this._heap[j])
  }
  push(node: T) {
    this._heap.push(node)
    let cur = this._heap.length - 1
    let parent = (cur - 1) >> 1
    while (cur > 0 && this.comparator(cur, parent)) {
      this.swap(cur, parent)
      ;[cur, parent] = [parent, (parent - 1) >> 1]
    }
  }
  pop() {
    if (this.size() === 0) return null

    let res = this._heap[0]
    this.swap(0, this._heap.length - 1)
    this._heap.pop()
    let cur = 0,
      left = 2 * cur + 1,
      right = 2 * cur + 2

    while (left < this._heap.length) {
      if (!this._has(right)) right = left
      if (this.comparator(right, left)) [left, right] = [right, left]
      if (this.comparator(cur, left)) break

      this.swap(cur, left)
      cur = left
      ;[left, right] = [2 * cur + 1, 2 * cur + 2]
    }
    return res
  }
  top() {
    if (this.size() === 0) return null

    return this._heap[0]
  }
  size() {
    return this._heap.length
  }
}

test.each([
  {
    input: {
      n: 5,
      edges: [
        [1, 2],
        [1, 3],
        [1, 4],
        [3, 4],
        [4, 5],
      ],
      time: 3,
      change: 5,
    },
    output: 13,
  },
  { input: { n: 2, edges: [[1, 2]], time: 3, change: 2 }, output: 11 },
])(
  'input: n = $input.n, edges = $input.edges, time = $input.time, change = $input.change',
  ({ input: { n, edges, time, change }, output }) => {
    expect(secondMinimum(n, edges, time, change)).toEqual(output)
  },
)