AtCoder Beginner Contest 320 D

https://atcoder.jp/contests/abc320/tasks/abc320_d

グラフを作って1からたどります。

// Relative Position
#![allow(non_snake_case)]

//////////////////// 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()
}


//////////////////// Point ////////////////////

use std::ops::{Add, Sub, Neg};

#[derive(Clone, Copy)]
struct Point {
    x: i64,
    y: i64,
}

impl Add for Point {
    type Output = Self;
    
    fn add(self, other: Self) -> Self {
        Self { x: self.x + other.x, y: self.y + other.y }
    }
}

impl Sub for Point {
    type Output = Self;
    
    fn sub(self, other: Self) -> Self {
        Self { x: self.x - other.x, y: self.y - other.y }
    }
}

impl Neg for Point {
    type Output = Self;
    
    fn neg(self) -> Self {
        Self { x: -self.x, y: -self.y }
    }
}

impl Point {
    fn new(x: i64, y: i64) -> Point {
        Point { x, y }
    }
}


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

use std::collections::HashMap;

type Node = usize;
type Edge = (Node, Node, Point);
type Graph = Vec<HashMap<Node, Point>>;

fn read_edge() -> Edge {
    let v = read_vec::<i64>();
    ((v[0]-1) as usize, (v[1]-1) as usize, Point::new(v[2], v[3]))
}

fn make_graph(N: usize, edges: Vec<Edge>) -> Graph {
    let mut graph: Graph = (0..N).map(|_| HashMap::new()).collect();
    for (v, w, pt) in edges.into_iter() {
        graph[v].insert(w, pt);
        graph[w].insert(v, -pt);
    }
    graph
}

fn walk(v0: Node, graph: &Graph) -> Vec<Option<Point>> {
    let N = graph.len();
    let mut positions: Vec<Option<Point>> = vec![None; N];
    positions[0] = Some(Point::new(0, 0));
    let mut stk: Vec<Node> = vec![v0];
    while let Some(v) = stk.pop() {
        let pt0 = positions[v].unwrap();
        for (&w, &pt) in graph[v].iter() {
            if positions[w].is_none() {
                stk.push(w);
                positions[w] = Some(pt0 + pt)
            }
        }
    }
    positions
}


//////////////////// 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_edge()).collect();
    (N, edges)
}

fn F(N: usize, edges: Vec<Edge>) {
    let graph = make_graph(N, edges);
    let positions = walk(0, &graph);
    for pos in positions.into_iter() {
        match pos {
            Some(pt) => println!("{} {}", pt.x, pt.y),
            None     => println!("undecidable")
        }
    }
}

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