#1175574 (Rust) No.3669 误差绝不允许

• 問題: No.3669 误差绝不允许
• ユーザー: harurun
• 提出日時: 2026-08-07 04:23:26
• 言語: Rust (1.97.1 + proconio + num + itertools)
• 結果: AC
• 実行時間: 330 ms / 3,000 ms
• コード長: 5,957 bytes
• コンパイル時間: 11,586 ms
• コンパイル使用メモリ: 196,868 KB
• 実行使用メモリ: 28,084 KB
• 最終ジャッジ日時: 2026-09-04 22:11:06
• 合計ジャッジ時間: 18,615 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 2
other	AC * 30

ソースコード

use num::bigint::BigInt;
use num::Zero;
use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::io::{self, Read, Write};
use std::str::FromStr;

const MAX_AB: usize = 300;

struct RawEdge {
    u: usize,
    v: usize,
    numerator: usize,
    denominator: usize,
}

struct Edge {
    to: usize,
    weight: BigInt,
}

#[derive(Eq, PartialEq)]
struct State {
    distance: BigInt,
    vertex: usize,
}

// RustのBinaryHeapは最大ヒープなので、比較を逆転させて最小ヒープにする。
impl Ord for State {
    fn cmp(&self, other: &Self) -> Ordering {
        other
            .distance
            .cmp(&self.distance)
            .then_with(|| other.vertex.cmp(&self.vertex))
    }
}

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

struct Scanner {
    input: Vec<u8>,
    index: usize,
}

impl Scanner {
    fn new() -> Self {
        let mut input = String::new();
        io::stdin().read_to_string(&mut input).unwrap();

        Self {
            input: input.into_bytes(),
            index: 0,
        }
    }

    fn next<T: FromStr>(&mut self) -> T {
        while self.index < self.input.len()
            && self.input[self.index].is_ascii_whitespace()
        {
            self.index += 1;
        }

        let start = self.index;

        while self.index < self.input.len()
            && !self.input[self.index].is_ascii_whitespace()
        {
            self.index += 1;
        }

        std::str::from_utf8(&self.input[start..self.index])
            .unwrap()
            .parse()
            .ok()
            .unwrap()
    }
}

fn main() {
    let mut scanner = Scanner::new();

    let n: usize = scanner.next();
    let m: usize = scanner.next();

    let mut raw_edges = Vec::with_capacity(m);

    // maximum_exponent[p]は、いずれかのb_iに現れるpの指数の最大値。
    let mut maximum_exponent = vec![0usize; MAX_AB + 1];

    for _ in 0..m {
        let mut u: usize = scanner.next();
        let mut v: usize = scanner.next();
        let a: usize = scanner.next();
        let b: usize = scanner.next();

        u -= 1;
        v -= 1;

        raw_edges.push(RawEdge {
            u,
            v,
            numerator: a,
            denominator: b,
        });

        let mut value = b;
        let mut prime = 2;

        while prime * prime <= value {
            if value % prime != 0 {
                prime += 1;
                continue;
            }

            let mut exponent = 0;

            while value % prime == 0 {
                value /= prime;
                exponent += 1;
            }

            maximum_exponent[prime] =
                maximum_exponent[prime].max(exponent);

            prime += 1;
        }

        if value > 1 {
            maximum_exponent[value] =
                maximum_exponent[value].max(1);
        }
    }

    // すべてのb_iを割り切る共通分母を構築する。
    let mut common_denominator = BigInt::from(1usize);
    let mut prime_powers: Vec<(BigInt, usize)> = Vec::new();

    for prime in 2..=MAX_AB {
        let exponent = maximum_exponent[prime];

        if exponent == 0 {
            continue;
        }

        let prime_bigint = BigInt::from(prime);
        prime_powers.push((prime_bigint.clone(), exponent));

        for _ in 0..exponent {
            common_denominator *= &prime_bigint;
        }
    }

    let mut graph: Vec<Vec<Edge>> =
        (0..n).map(|_| Vec::new()).collect();

    for raw in raw_edges {
        let mut scaled_weight = common_denominator.clone();
        scaled_weight /= raw.denominator;
        scaled_weight *= raw.numerator;

        // 無向辺なので、一方では複製し、もう一方では所有権を移動する。
        graph[raw.u].push(Edge {
            to: raw.v,
            weight: scaled_weight.clone(),
        });

        graph[raw.v].push(Edge {
            to: raw.u,
            weight: scaled_weight,
        });
    }

    let mut distance = vec![BigInt::zero(); n];
    let mut reached = vec![false; n];

    let mut queue = BinaryHeap::new();

    reached[0] = true;
    distance[0] = BigInt::zero();

    queue.push(State {
        distance: BigInt::zero(),
        vertex: 0,
    });

    while let Some(current) = queue.pop() {
        if !reached[current.vertex]
            || current.distance != distance[current.vertex]
        {
            continue;
        }

        for edge in &graph[current.vertex] {
            // 多倍長整数の加算を一度だけ行う。
            let next_distance = &current.distance + &edge.weight;

            if !reached[edge.to] || next_distance < distance[edge.to] {
                reached[edge.to] = true;
                distance[edge.to] = next_distance.clone();

                queue.push(State {
                    distance: next_distance,
                    vertex: edge.to,
                });
            }
        }
    }

    // 出力全体をStringに格納してから一度に書き込む。
    let mut output = String::with_capacity(8 * 1024 * 1024);

    for vertex in 1..n {
        let mut numerator = distance[vertex].clone();
        let mut denominator = common_denominator.clone();

        // 分母の素因数分解は既知なので、各素数で約分する。
        for (prime, exponent) in &prime_powers {
            for _ in 0..*exponent {
                if !(&numerator % prime).is_zero() {
                    break;
                }

                numerator /= prime;
                denominator /= prime;
            }
        }

        output.push_str(&numerator.to_string());
        output.push(' ');
        output.push_str(&denominator.to_string());
        output.push('\n');
    }

    let stdout = io::stdout();
    let mut writer = io::BufWriter::new(stdout.lock());
    writer.write_all(output.as_bytes()).unwrap();
}