競プロ典型 013

https://atcoder.jp/contests/typical90/tasks/typical90_m

1とNと両方からダイクストラをやればよいです。

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


//////////////////// Item ////////////////////

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

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

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

impl Item {
    fn new(v: Node, w: Weight) -> Item {
        Item { v, w }
    }
}


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

type Node = usize;
type Weight = i32;
type Edge = (Node, Node, Weight);
type Graph = Vec<Vec<(Node, Weight)>>;

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

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

fn Dijkstra(v0: Node, graph: &Graph) -> Vec<Weight> {
    let N = graph.len();
    let mut dists: Vec<Weight> = vec![-1; N];
    let mut heap = BinaryHeap::new();
    heap.push(Item::new(v0, 0));
    while let Some(item) = heap.pop() {
        if dists[item.v] == -1 {
            dists[item.v] = item.w
        }
        for &(v, w) in graph[item.v].iter() {
            if dists[v] == -1 {
                heap.push(Item::new(v, item.w + w))
            }
        }
    }
    dists
}


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

fn read_input() -> (usize, Vec<Edge>) {
    let v = read_vec();
    let (N, M) = (v[0], 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 d1 = Dijkstra(0, &graph);
    let d2 = Dijkstra(N-1, &graph);
    for v in 0..N {
        println!("{}", d1[v] + d2[v])
    }
}

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