結果

問題 No.807 umg tours
コンテスト
ユーザー akakimidori
提出日時 2019-11-06 17:53:06
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 579 ms / 4,000 ms
コード長 4,289 bytes
コンパイル時間 12,481 ms
コンパイル使用メモリ 379,056 KB
実行使用メモリ 50,176 KB
最終ジャッジ日時 2024-11-23 19:44:11
合計ジャッジ時間 18,271 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

// ---------- begin pairing heap (min) ----------
#[allow(dead_code)]
mod pairing {
    use std;
    // min heap
    pub struct Heap<T: Ord> {
        root: Link<T>,
        size: usize,
    }
    impl<T: Ord> Heap<T> {
        pub fn new() -> Heap<T> {
            Heap {
                root: None,
                size: 0,
            }
        }
        pub fn push(&mut self, val: T) {
            let a = self.root.take();
            let b = Some(Node::new_node(val));
            self.root = Node::meld(a, b);
            self.size += 1;
        }
        pub fn pop(&mut self) -> Option<T> {
            self.root.take().map(|mut root| {
                self.size -= 1;
                let lst = root.child.take();
                self.root = Node::merge_list(lst);
                root.val
            })
        }
        pub fn peek(&self) -> Option<&T> {
            self.root.as_ref().map(|root| &root.val)
        }
        pub fn len(&self) -> usize {
            self.size
        }
        pub fn clear(&mut self) {
            self.root = None;
            self.size = 0;
        }
        pub fn is_empty(&self) -> bool {
            self.len() > 0
        }
    }
    type NonNull<T> = Box<Node<T>>;
    type Link<T> = Option<NonNull<T>>;
    struct Node<T> {
        val: T,
        next: Link<T>,
        child: Link<T>,
    }
    impl<T: Ord> Node<T> {
        fn new_node(val: T) -> NonNull<T> {
            Box::new(Node {
                val: val,
                next: None,
                child: None,
            })
        }
        fn meld(a: Link<T>, b: Link<T>) -> Link<T> {
            if a.is_none() {
                return b;
            }
            if b.is_none() {
                return a;
            }
            let mut a = a.unwrap();
            let mut b = b.unwrap();
            match a.val.cmp(&b.val) {
                std::cmp::Ordering::Less => {
                    b.next = a.child.take();
                    a.child = Some(b);
                    Some(a)
                },
                _ => {
                    a.next = b.child.take();
                    b.child = Some(a);
                    Some(b)
                },
            }
        }
        fn merge_list(mut lst: Link<T>) -> Link<T> {
            let mut r = None;
            while !lst.is_none() {
                let mut a = lst.take().unwrap();
                lst = a.next.take();
                if lst.is_none() {
                    lst = Some(a);
                    break;
                } else {
                    let mut b = lst.take().unwrap();
                    lst = b.next.take();
                    r = Node::meld(r, Node::meld(Some(a), Some(b)));
                }
            }
            if !lst.is_none() {
                r = Node::meld(r, lst);
            }
            r
        }
    }
}
// ---------- end pairing heap (min) ----------

use std::io::Read;
use std::io::Write;

fn run() {
    let out = std::io::stdout();
    let mut out = std::io::BufWriter::new(out.lock());
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let n: usize = it.next().unwrap().parse().unwrap();
    let m: usize = it.next().unwrap().parse().unwrap();
    let mut g = vec![vec![]; 2 * n];
    for _ in 0..m {
        let a = it.next().unwrap().parse::<usize>().unwrap() - 1;
        let b = it.next().unwrap().parse::<usize>().unwrap() - 1;
        let c = it.next().unwrap().parse::<u64>().unwrap();
        g[a].push((b, c));
        g[b].push((a, c));
        g[a].push((b + n, 0));
        g[b].push((a + n, 0));
        g[a + n].push((b + n, c));
        g[b + n].push((a + n, c));
    }
    let inf = std::u64::MAX;
    let mut dp = vec![inf; 2 * n];
    dp[0] = 0;
    dp[n] = 0;
    let mut h = pairing::Heap::<(u64, usize)>::new();
    h.push((0, 0));
    while let Some(s) = h.pop() {
        if s.0 > dp[s.1] {
            continue;
        }
        for &(u, w) in &g[s.1] {
            let d = s.0 + w;
            if dp[u] > d {
                dp[u] = d;
                h.push((d, u));
            }
        }
    }
    for i in 0..n {
        let d = dp[i] + dp[i + n];
        writeln!(out, "{}", d).ok();
    }
}

fn main() {
    run();
}
0