結果

問題 No.807 umg tours
ユーザー akakimidori
提出日時 2019-11-06 17:58:17
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 370 ms / 4,000 ms
コード長 4,405 bytes
コンパイル時間 13,466 ms
コンパイル使用メモリ 385,280 KB
実行使用メモリ 49,440 KB
最終ジャッジ日時 2024-11-23 19:43:32
合計ジャッジ時間 17,720 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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();
            if a.val > b.val {
                std::mem::swap(&mut a, &mut b);
            }
            b.next = a.child.take();
            a.child = Some(b);
            Some(a)
        }
        fn merge_list(mut lst: Link<T>) -> Link<T> {
            let mut r = None;
            while lst.is_some() {
                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;

use std::cmp::*;

#[derive(Eq, PartialEq)]
struct State {
    v: usize,
    d: u64,
}

impl Ord for State {
    fn cmp(&self, rhs: &Self) -> Ordering {
        self.d.cmp(&rhs.d)
    }
}

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

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::new();
    h.push(State{v: 0, d: 0});
    while let Some(s) = h.pop() {
        if s.d > dp[s.v] {
            continue;
        }
        for &(u, w) in &g[s.v] {
            let d = s.d + w;
            if dp[u] > d {
                dp[u] = d;
                h.push(State{v: u, d: d});
            }
        }
    }
    for i in 0..n {
        let d = dp[i] + dp[i + n];
        writeln!(out, "{}", d).ok();
    }
}

fn main() {
    run();
}
0