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

/// Adjacency list where `graph[u]` contains `(v, weight)` edges from `u` to `v`.
pub type Graph = Vec<Vec<(usize, u64)>>;

/// Computes shortest distances from `start` using Dijkstra's algorithm.
///
/// Returns `None` for unreachable vertices. Edge weights must be non-negative,
/// which is guaranteed here by using `u64`.
pub fn dijkstra(graph: &[Vec<(usize, u64)>], start: usize) -> Vec<Option<u64>> {
    let n = graph.len();
    let mut dist = vec![u64::MAX; n];
    let mut heap = BinaryHeap::new();

    if start >= n {
        return vec![None; n];
    }

    dist[start] = 0;
    heap.push((Reverse(0), start));

    while let Some((Reverse(cost), u)) = heap.pop() {
        // Skip stale heap entries that no longer match the best known distance.
        if cost != dist[u] {
            continue;
        }

        for &(v, weight) in &graph[u] {
            if v >= n {
                continue;
            }

            let Some(next_cost) = cost.checked_add(weight) else {
                continue;
            };

            if next_cost < dist[v] {
                dist[v] = next_cost;
                heap.push((Reverse(next_cost), v));
            }
        }
    }

    dist.into_iter()
        .map(|d| if d == u64::MAX { None } else { Some(d) })
        .collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn finds_shortest_paths() {
        let graph: Graph = vec![
            vec![(1, 4), (2, 1)],
            vec![(3, 1)],
            vec![(1, 2), (3, 5)],
            vec![],
        ];

        assert_eq!(dijkstra(&graph, 0), vec![Some(0), Some(3), Some(1), Some(4)]);
    }

    #[test]
    fn reports_unreachable_vertices() {
        let graph: Graph = vec![
            vec![(1, 7)],
            vec![],
            vec![(0, 3)],
        ];

        assert_eq!(dijkstra(&graph, 0), vec![Some(0), Some(7), None]);
    }
}