アルゴリズムと数学 044

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_an

各辺の距離を1として、ダイクストラ法を使えばよいです。
PriorityQueueは、BinaryHeapで実装できます。

// Shortest Path 1
#![allow(non_snake_case)]

use std::collections::BinaryHeap;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Graph ////////////////////

type Node = usize;
type Edge = (Node, Node);
type Weight = i32;

#[derive(Debug, Eq, PartialEq)]
struct Item {
    dist: i32,
    node: Node,
}

impl Ord for Item {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.dist.cmp(&self.dist)
    }
}

impl PartialOrd for Item {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

struct Graph {
    g: Vec<Vec<(Node, Weight)>>
}

impl Graph {
    fn find_shortest_distances(&self) -> Vec<i32> {
        let mut heap = BinaryHeap::new();
        heap.push(Item { dist: 0, node: 0 });
        let mut dists: Vec<i32> = self.g.iter().map(|_| -1).collect();
        while let Some(Item { dist, node }) = heap.pop() {
            if dists[node] == -1 {
                dists[node] = dist;
            }
            for (neighbor, d) in self.g[node].iter() {
                if dists[*neighbor] == -1 {
                    heap.push(Item { dist: dist + d, node: *neighbor })
                }
            }
        }
        dists
    }
    
    fn create_from_edges(N: usize, edges: Vec<Edge>) -> Graph {
        let mut g: Vec<Vec<(Node, Weight)>> = (0..N).map(|_| vec![]).collect();
        for (v, w) in edges.into_iter() {
            g[v].push((w, 1));
            g[w].push((v, 1))
        }
        Graph { g }
    }
}


//////////////////// process ////////////////////

fn read_input() -> (usize, Vec<Edge>) {
    let v = read_vec();
    let N: usize = v[0];
    let M: usize = v[1];
    let edges: Vec<Edge> = (0..M).map(|_| read_vec::<Node>()).
                                    map(|u| (u[0]-1, u[1]-1)).collect();
    (N, edges)
}

fn main() {
    let (N, edges) = read_input();
    let graph = Graph::create_from_edges(N, edges);
    let dists = graph.find_shortest_distances();
    for d in dists.into_iter() {
        println!("{}", d)
    }
}