AtCoder Beginner Contest 362 D

https://atcoder.jp/contests/abc362/tasks/abc362_d

ほぼダイクストラ法ですね。

// Shortest Path 3
#![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 Node = usize;
type Weight = i64;
type Edge = (Node, Node, Weight);
type Graph = Vec<Vec<(Node, Weight)>>;

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

fn create_graph(N: usize, edges: Vec<Edge>) -> Graph {
    let mut graph: Graph = vec![vec![]; N];
    for (U, V, B) in edges.into_iter() {
        graph[U].push((V, B));
        graph[V].push((U, B))
    }
    graph
}


//////////////////// BinaryHeap ////////////////////

use std::collections::BinaryHeap;


#[derive(Debug, Eq, PartialEq)]
struct Item {
    weight: Weight,
    node: Node,
}

impl Ord for Item {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.weight.cmp(&self.weight)
    }
}

impl PartialOrd for Item {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}


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

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

fn F(A: Vec<Weight>, edges: Vec<Edge>) {
    let N = A.len();
    let graph = create_graph(N, edges);
    let mut weights: Vec<Weight> = vec![-1; N];
    let mut tree = BinaryHeap::<Item>::new();
    tree.push(Item { weight: A[0], node: 0 });
    while let Some(item) = tree.pop() {
        if weights[item.node] != -1 {
            continue
        }
        
        weights[item.node] = item.weight;
        for &(v, w) in graph[item.node].iter() {
            if weights[v] == -1 {
                tree.push(Item { weight: item.weight + w + A[v], node: v })
            }
        }
    }
    
    println!("{}", (1..N).map(|i| weights[i].to_string()).
                                        collect::<Vec<String>>().join(" "))
}

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