結果

問題 No.3669 误差绝不允许
コンテスト
ユーザー urectanc
提出日時 2026-09-04 23:33:11
言語 Rust
(1.97.1 + proconio + num + itertools)
コンパイル:
/usr/bin/rustc_custom
実行:
./target/release/main
結果
AC  
実行時間 2,024 ms / 3,000 ms
+ 268µs
コード長 1,194 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 7,367 ms
コンパイル使用メモリ 199,976 KB
実行使用メモリ 23,168 KB
最終ジャッジ日時 2026-09-04 23:33:36
合計ジャッジ時間 17,683 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

use std::{cmp::Reverse, collections::BinaryHeap};

use num::{BigInt, BigRational, Zero};
use proconio::{fastout, input, marker::Usize1};

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

    let mut graph = vec![vec![]; n];
    for &(u, v, a, b) in &edges {
        let a = BigInt::zero() + a;
        let b = BigInt::zero() + b;
        let r = BigRational::new(a, b);
        graph[u].push((v, r.clone()));
        graph[v].push((u, r));
    }

    let mut heap = BinaryHeap::new();
    let mut dist = vec![None; n];
    heap.push((Reverse(BigRational::zero()), 0));
    dist[0] = Some(BigRational::zero());

    while let Some((Reverse(d), v)) = heap.pop() {
        if dist[v].as_ref().is_some_and(|d_v| d_v != &d) {
            continue;
        }

        for &(u, ref w) in &graph[v] {
            let nd = &d + w;
            if dist[u].as_ref().is_none_or(|d_u| d_u > &nd) {
                dist[u] = Some(nd.clone());
                heap.push((Reverse(nd), u));
            }
        }
    }

    for r in &dist[1..] {
        let r = r.as_ref().unwrap();
        println!("{} {}", r.numer(), r.denom());
    }
}
0