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

/// Computes shortest distances from `start` using Dijkstra's algorithm.
///
/// The graph is an adjacency list where `graph[u]` contains `(v, weight)` edges.
/// All edge weights must be non-negative, which is enforced here by using `u64`.
pub fn dijkstra(graph: &[Vec<(usize, u64)>], start: usize) -> Vec<Option<u64>> {
    let n = graph.len();
    let mut dist = vec![None; n];

    if start >= n {
        return dist;
    }

    let mut heap = BinaryHeap::new();

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

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

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

            let Some(next_dist) = current_dist.checked_add(weight) else {
                continue;
            };

            if dist[next].map_or(true, |best| next_dist < best) {
                dist[next] = Some(next_dist);
                heap.push(Reverse((next_dist, next)));
            }
        }
    }

    dist
}

fn main() {}

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

    #[test]
    fn finds_shortest_paths() {
        let 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 leaves_unreachable_nodes_as_none() {
        let graph = vec![vec![(1, 7)], vec![], vec![(0, 3)]];

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