Rewrite: BinaryHeap Dijkstra

pub fn dijkstra(n: usize, edges: &Vec<(usize, usize, u64)>, src: usize) -> Vec<Option<u64>> {
    let mut adj: Vec<Vec<(usize, u64)>> = vec![Vec::new(); n];
    for &(u, v, w) in edges { adj[u].push((v, w)); }
    let mut dist: Vec<Option<u64>> = vec![None; n];
    let mut done = vec![false; n];
    dist[src] = Some(0);
    for _ in 0..n {
        let mut u: Option<usize> = None;
        for i in 0..n {
            if done[i] || dist[i].is_none() { continue; }
            if u.map_or(true, |j| dist[i].unwrap() < dist[j].unwrap()) { u= Some(i); }
        }
        let u= match u { Some(u)=> u, None=> break };
        done[u]= true;
        let du= dist[u].unwrap();
        for &(v, w) in &adj[u] {
            let nd= du + w;
            if dist[v].map_or(true, |cv| nd < cv) { dist[v]= Some(nd); }
        }
    }
    dist
}

function dijkstra(n: number, edges: number[][], src: number): Array<number | null> {
  const adj: Array<Array<[number, number]>> = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) adj[u].push([v, w]);
  const dist: Array<number | null> = new Array(n).fill(null);
  const done = new Array(n).fill(false);
  dist[src] = 0;
  for (let _ = 0; _ < n; _++) {
    let u= -1;
    for (let i= 0; i < n; i++) {
      if (done[i] || dist[i]= null) continue;
      if (u= -1 || dist[i]! < dist[u]!) u= i;
    }
    if (u= -1) break;
    done[u]= true;
    for (const [v, w] of adj[u]) {
      const nd= dist[u]! + w;
      if (dist[v]= null || nd < dist[v]!) dist[v]= nd;
    }
  }
  return dist;
}

use std::cmp::Reverse;
use std::collections::BinaryHeap;

pub fn dijkstra(n: usize, edges: &Vec<(usize, usize, u64)>, src: usize) -> Vec<Option<u64>> {
    let mut adj: Vec<Vec<(usize, u64)>> = vec![Vec::new(); n];
    for &(u, v, w) in edges { adj[u].push((v, w)); }

    let mut dist: Vec<Option<u64>> = vec![None; n];
    dist[src] = Some(0);

    let mut heap: BinaryHeap<Reverse<(u64, usize)>> = BinaryHeap::new();
    heap.push(Reverse((0, src)));

    while let Some(Reverse((d, u))) = heap.pop() {
        if let Some(cur) = dist[u] {
            if d > cur { continue; }
        }
        for &(v, w) in &adj[u] {
            let nd = d + w;
            if dist[v].map_or(true, |cv| nd < cv) {
                dist[v]= Some(nd);
                heap.push(Reverse((nd, v)));
            }
        }
    }

    dist
}

class MinHeap<T> {
  private a: T[] = [];
  constructor(private less: (a: T, b: T) => boolean) {}
  size(): number { return this.a.length; }
  push(v: T): void { this.a.push(v); this.up(this.a.length - 1); }
  pop(): T | undefined {
    if (this.a.length === 0) return undefined;
    const top = this.a[0];
    const last = this.a.pop()!;
    if (this.a.length > 0) { this.a[0] = last; this.down(0); }
    return top;
  }
  private up(i: number): void {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (!this.less(this.a[i], this.a[p])) break;
      [this.a[p], this.a[i]] = [this.a[i], this.a[p]];
      i = p;
    }
  }
  private down(i: number): void {
    const n = this.a.length;
    while (true) {
      const l = 2 * i + 1, r = l + 1;
      let best = i;
      if (l < n && this.less(this.a[l], this.a[best])) best= l;
      if (r < n && this.less(this.a[r], this.a[best])) best= r;
      if (best= i) break;
      [this.a[best], this.a[i]]= [this.a[i], this.a[best]];
      i= best;
    }
  }
}

function dijkstra(n: number, edges: number[][], src: number): Array<number | null> {
  const adj: Array<Array<[number, number]>> = Array.from({ length: n }, () => []);
  for (const [u, v, w] of edges) adj[u].push([v, w]);

  const dist: Array<number | null> = new Array(n).fill(null);
  dist[src] = 0;

  const heap = new MinHeap<[number, number]>((a, b) => a[0] < b[0]);
  heap.push([0, src]);

  while (heap.size() > 0) {
    const [d, u] = heap.pop()!;
    if (dist[u] !== null && d > dist[u]!) continue;
    for (const [v, w] of adj[u]) {
      const nd = d + w;
      if (dist[v] === null || nd < dist[v]!) {
        dist[v]= nd;
        heap.push([nd, v]);
      }
    }
  }

  return dist;
}