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

/// Directed weighted graph represented as `graph[node] = [(neighbor, weight)]`.
type Graph = Vec<Vec<(usize, u64)>>;

/// Returns the shortest distances from `start`.
/// Unreachable nodes have distance `None`.
fn dijkstra(graph: &Graph, start: usize) -> Vec<Option<u64>> {
    let mut distances = vec![None; graph.len()];
    if start >= graph.len() {
        return distances;
    }

    let mut queue = BinaryHeap::new();
    distances[start] = Some(0);
    queue.push(Reverse((0_u64, start)));

    while let Some(Reverse((distance, node))) = queue.pop() {
        // Ignore entries superseded by a shorter path.
        if distances[node] != Some(distance) {
            continue;
        }

        for &(neighbor, weight) in &graph[node] {
            assert!(neighbor < graph.len(), "edge points to an invalid node");

            // Overflow cannot produce a valid u64 path length.
            let Some(candidate) = distance.checked_add(weight) else {
                continue;
            };

            if distances[neighbor].is_none_or(|known| candidate < known) {
                distances[neighbor] = Some(candidate);
                queue.push(Reverse((candidate, neighbor)));
            }
        }
    }

    distances
}

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

    println!("{:?}", dijkstra(&graph, 0));
}

#[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 leaves_unreachable_nodes_unset() {
        let graph: Graph = vec![vec![(1, 7)], vec![], vec![]];

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