q013scratch.rs

use proconio::{input, marker::Usize1, fastout};
use std::collections::BinaryHeap;
use std::cmp::Reverse;
const MAX: i64 = std::i64::MAX;

#[allow(dead_code)]
struct Graph {
    n: usize,
    m: usize,
    edges: Vec<Vec<(usize, usize, i64)>>,
}
impl Graph {
    fn dijkstra(&self, k: usize) -> Vec<i64> {
        let mut pq = BinaryHeap::new();
        pq.push( (Reverse(0), k) );
        let mut dist = vec![MAX; self.n];
        dist[k] = 0;
        while let Some( (Reverse(dx), x) ) = pq.pop() {
            if dx > dist[x] { continue; }
            for &(_i, y, ew) in &self.edges[x] {
                let dy = dx + ew;
                if dy < dist[y] {
                	dist[y] = dy;
                    pq.push( (Reverse(dy), y) );
                }
            }
        }
        dist
    }
}

#[fastout]
fn main() {
    input! { n: usize, m: usize, abc: [(Usize1, Usize1, i64); m], };

    let mut edges = vec![vec![]; n];
    for (i, &(a, b, c)) in abc.iter().enumerate() {
        edges[a].push( (i, b, c) );
        edges[b].push( (i, a, c) );
    }
    let g = Graph { n, m, edges, };

    let dist1 = g.dijkstra(0);
    let distn = g.dijkstra(n-1);
    let mut ans = vec![0; n];
    for i in 0..n {
        ans[i] = dist1[i] + distn[i];
    }

    for i in 0..n {
        println!("{}", ans[i]);
    }
}