use std::cmp::Reverse;
use std::collections::BinaryHeap;
use crate::utils::num_traits::{Bounded, Zero};
#[allow(clippy::ptr_arg)]
pub fn dijkstra<T: Copy + Zero + Bounded + Ord>(
graph: &Vec<Vec<(usize, T)>>,
s: usize,
) -> (Vec<Option<usize>>, Vec<T>) {
let n: usize = graph.len();
let mut prev = vec![None; n];
let mut dist = vec![T::max_value(); n];
let mut pq: BinaryHeap<Reverse<(T, usize)>> = BinaryHeap::new();
dist[s] = T::zero();
pq.push(Reverse((dist[s], s)));
while let Some(Reverse((cost, u))) = pq.pop() {
if dist[u] < cost {
continue;
}
for &(v, weight) in &graph[u] {
if dist[v] > dist[u] + weight {
prev[v] = Some(u);
dist[v] = dist[u] + weight;
pq.push(Reverse((dist[v], v)));
}
}
}
(prev, dist)
}
#[allow(clippy::ptr_arg)]
pub fn path_reconstruction(s: usize, t: usize, prev: &Vec<Option<usize>>) -> Option<Vec<usize>> {
if prev[s].is_some() || prev[t].is_none() {
return None;
}
let mut cur = t;
let mut path = vec![t];
while cur != s {
cur = prev[cur]?;
path.push(cur);
}
path.reverse();
Some(path)
}