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