アルゴリズムと数学 078

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

距離をQueueを使って求めるのですが、120が上限を忘れないように。

// Distance Sum
#![allow(non_snake_case)]

use std::cmp::min;
use std::collections::VecDeque;


//////////////////// 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 Graph = Vec<Vec<Node>>;

fn create_graph(N: usize, edges: Vec<Edge>) -> Graph {
    let mut graph: Graph = (0..N).map(|_| vec![]).collect();
    for (u, v) in edges.into_iter() {
        graph[u].push(v);
        graph[v].push(u)
    }
    graph
}


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

fn read_edge() -> Edge {
    let v: Vec<usize> = read_vec();
    (v[0]-1, v[1]-1)
}

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

fn f(N: usize, edges: Vec<Edge>) {
    let graph = create_graph(N, edges);
    let mut max_dists: Vec<i32> = vec![-1; N];
    let mut queue: VecDeque<Node> = VecDeque::new();
    max_dists[0] = 0;
    queue.push_back(0);
    while let Some(v) = queue.pop_front() {
        for &u in graph[v].iter() {
            if max_dists[u] == -1 {
                max_dists[u] = min(max_dists[v] + 1, 120);
                queue.push_back(u)
            }
        }
    }
    
    for v in 0..N {
        if max_dists[v] == -1 {
            max_dists[v] = 120
        }
    }
    
    for dist in max_dists.into_iter() {
        println!("{}", dist)
    }
}

fn main() {
    let (N, edges) = read_input();
    f(N, edges)
}