アルゴリズムと数学 080

https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_bl

ダイクストラ法ですね。

// Difference Optimization 2
#![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 Dist = i64;
type Edge = (Node, Node, Dist);
type Graph = Vec<Vec<(Node, Dist)>>;

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

fn create_graph(N: usize, edges: Vec<Edge>) -> Graph {
    let mut graph: Graph = (0..N).map(|_| vec![]).collect();
    for (u, v, d) in edges.into_iter() {
        graph[u].push((v, d));
        graph[v].push((u, d))
    }
    graph
}


//////////////////// Neighbor ////////////////////

#[derive(Debug, Eq, PartialEq)]
struct Neighbor {
    node: Node,
    dist: Dist
}

impl Neighbor {
    fn new(node: Node, dist: Dist) -> Neighbor {
        Neighbor { node, dist }
    }
}

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

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


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

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

fn f(N: usize, edges: Vec<Edge>) -> i64 {
    let graph = create_graph(N, edges);
    let mut dists = vec![-1; N];
    let mut heap = BinaryHeap::new();
    heap.push(Neighbor::new(0, 0));
    while let Some(nei) = heap.pop() {
        if dists[nei.node] != -1 {
            continue
        }
        dists[nei.node] = nei.dist;
        for &(v, d) in graph[nei.node].iter() {
            if dists[v] == -1 {
                heap.push(Neighbor::new(v, nei.dist + d))
            }
        }
    }
    dists[N-1]
}

fn main() {
    let (N, edges) = read_input();
    println!("{}", f(N, edges))
}