AtCoder Beginner Contest 305 E

https://atcoder.jp/contests/abc305/tasks/abc305_e

PriorityQueueに(進める距離, ノード番号)を格納してグラフを進んでいくとよいです。

// Art Gallery on Graph
#![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 Graph = Vec<Vec<Node>>;

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

fn make_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_guard() -> (Node, i32) {
    let v: Vec<usize> = read_vec();
    (v[0]-1, v[1] as i32)
}

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

fn f(N: usize, edges: Vec<Edge>, guards: Vec<(Node, i32)>) {
    let graph = make_graph(N, edges);
    let mut dists: Vec<i32> = (0..N).map(|_| -1).collect();
    let mut heap = BinaryHeap::new();
    for (p, h) in guards.into_iter() {
        heap.push((h, p))
    }
    
    while let Some((h, p)) = heap.pop() {
        if dists[p] == -1 {
            dists[p] = h
        }
        for &v in graph[p].iter() {
            if dists[v] != -1 {
                continue
            }
            dists[v] = h - 1;
            if h >= 1 {
                heap.push((h-1, v))
            }
        }
    }
    
    let vs: Vec<Node> = (0..N).filter(|&v| dists[v] != -1).collect();
    let ss: Vec<String> = vs.iter().map(|v| (v+1).to_string()).collect();
    println!("{}", ss.len());
    println!("{}", ss.join(" "))
}


//////////////////// main ////////////////////

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