AtCoder Beginner Contest 373 D

https://atcoder.jp/contests/abc373/tasks/abc373_d

有向グラフですが、逆方向に符号が反対の重みを持ったエッジを張って、適当に辿ればよいです。

//  Hidden Weights 
#![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()
}


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

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

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

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

impl Graph {
    fn len(&self) -> usize {
        self.g.len()
    }
    
    fn insert(&mut self, e: Edge) {
        let (u, v, w) = e;
        self.g[u].push((v, w));
        self.g[v].push((u, -w))
    }
    
    fn create_by_edges(N: usize, edges: Vec<Edge>) -> Graph {
        let g: Vec<Vec<(Node, Weight)>> = vec![vec![]; N];
        let mut graph = Graph { g };
        for edge in edges.into_iter() {
            graph.insert(edge)
        }
        graph
    }
}


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

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

fn walk_each(v0: Node, weights: &mut Vec<Weight>, graph: &Graph) {
    weights[v0] = 0;
    let mut stack: Vec<Node> = vec![v0];
    while let Some(u) = stack.pop() {
        for &(v, w) in graph.g[u].iter() {
            if weights[v] == i64::MIN {
                weights[v] = weights[u] + w;
                stack.push(v)
            }
        }
    }
}

fn walk(graph: &Graph) -> Vec<Weight> {
    let N = graph.len();
    let mut weights: Vec<Weight> = vec![i64::MIN; N];
    for v0 in 0..N {
        if weights[v0] == i64::MIN {
            walk_each(v0, &mut weights, graph)
        }
    }
    weights
}

fn F(N: usize, edges: Vec<Edge>) {
    let graph = Graph::create_by_edges(N, edges);
    let weights = walk(&graph);
    println!("{}", weights.iter().map(|w| w.to_string()).
                                    collect::<Vec<_>>().join(" "))
}

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