#1174993 (C++23(gcc16)) No.3669 误差绝不允许

• 問題: No.3669 误差绝不允许
• ユーザー: harurun
• 提出日時: 2026-08-05 01:55:31
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 324 ms / 3,000 ms
• コード長: 8,232 bytes
• コンパイル時間: 3,205 ms
• コンパイル使用メモリ: 235,688 KB
• 実行使用メモリ: 22,332 KB
• 最終ジャッジ日時: 2026-09-04 22:01:45
• 合計ジャッジ時間: 9,533 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

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

ソースコード

#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>

class BigUInt {
public:
    static constexpr std::uint32_t BASE = 1000000000U;

    BigUInt(std::uint64_t value = 0) {
        while (value > 0) {
            digits_.push_back(static_cast<std::uint32_t>(value % BASE));
            value /= BASE;
        }
    }

    bool isZero() const {
        return digits_.empty();
    }

    int compare(const BigUInt& other) const {
        if (digits_.size() != other.digits_.size()) {
            return digits_.size() < other.digits_.size() ? -1 : 1;
        }
        for (std::size_t i = digits_.size(); i-- > 0;) {
            if (digits_[i] != other.digits_[i]) {
                return digits_[i] < other.digits_[i] ? -1 : 1;
            }
        }
        return 0;
    }

    BigUInt& operator+=(const BigUInt& other) {
        const std::size_t size = std::max(digits_.size(), other.digits_.size());
        digits_.resize(size, 0);

        std::uint64_t carry = 0;
        for (std::size_t i = 0; i < size; ++i) {
            std::uint64_t current = carry + digits_[i];
            if (i < other.digits_.size()) {
                current += other.digits_[i];
            }
            digits_[i] = static_cast<std::uint32_t>(current % BASE);
            carry = current / BASE;
        }
        if (carry > 0) {
            digits_.push_back(static_cast<std::uint32_t>(carry));
        }
        return *this;
    }

    BigUInt& operator*=(std::uint32_t multiplier) {
        if (multiplier == 0 || isZero()) {
            digits_.clear();
            return *this;
        }

        std::uint64_t carry = 0;
        for (std::uint32_t& digit : digits_) {
            const std::uint64_t current =
                static_cast<std::uint64_t>(digit) * multiplier + carry;
            digit = static_cast<std::uint32_t>(current % BASE);
            carry = current / BASE;
        }
        while (carry > 0) {
            digits_.push_back(static_cast<std::uint32_t>(carry % BASE));
            carry /= BASE;
        }
        return *this;
    }

    // Returns the remainder. The quotient is stored in *this.
    std::uint32_t divideSmall(std::uint32_t divisor) {
        assert(divisor > 0);
        std::uint64_t remainder = 0;
        for (std::size_t i = digits_.size(); i-- > 0;) {
            const std::uint64_t current = remainder * BASE + digits_[i];
            digits_[i] = static_cast<std::uint32_t>(current / divisor);
            remainder = current % divisor;
        }
        normalize();
        return static_cast<std::uint32_t>(remainder);
    }

    std::uint32_t modSmall(std::uint32_t divisor) const {
        assert(divisor > 0);
        std::uint64_t remainder = 0;
        for (std::size_t i = digits_.size(); i-- > 0;) {
            remainder = (remainder * BASE + digits_[i]) % divisor;
        }
        return static_cast<std::uint32_t>(remainder);
    }

    std::string toString() const {
        if (isZero()) {
            return "0";
        }

        std::string result = std::to_string(digits_.back());
        for (std::size_t i = digits_.size() - 1; i-- > 0;) {
            const std::string block = std::to_string(digits_[i]);
            result.append(9 - block.size(), '0');
            result += block;
        }
        return result;
    }

    friend bool operator<(const BigUInt& lhs, const BigUInt& rhs) {
        return lhs.compare(rhs) < 0;
    }

    friend bool operator==(const BigUInt& lhs, const BigUInt& rhs) {
        return lhs.compare(rhs) == 0;
    }

    friend bool operator!=(const BigUInt& lhs, const BigUInt& rhs) {
        return !(lhs == rhs);
    }

private:
    std::vector<std::uint32_t> digits_;  // Little-endian, base 10^9.

    void normalize() {
        while (!digits_.empty() && digits_.back() == 0) {
            digits_.pop_back();
        }
    }
};

struct RawEdge {
    int u;
    int v;
    int numerator;
    int denominator;
};

struct Edge {
    int to;
    BigUInt weight;
};

struct State {
    BigUInt distance;
    int vertex;
};

struct StateGreater {
    bool operator()(const State& lhs, const State& rhs) const {
        const int comparison = lhs.distance.compare(rhs.distance);
        if (comparison != 0) {
            return comparison > 0;
        }
        return lhs.vertex > rhs.vertex;
    }
};

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;

    std::vector<RawEdge> rawEdges;
    rawEdges.reserve(m);

    std::vector<int> maximumExponent(1001, 0);

    for (int i = 0; i < m; ++i) {
        int u, v, a, b;
        std::cin >> u >> v >> a >> b;
        --u;
        --v;
        rawEdges.push_back({u, v, a, b});

        int value = b;
        for (int prime = 2; prime * prime <= value; ++prime) {
            if (value % prime != 0) {
                continue;
            }
            int exponent = 0;
            while (value % prime == 0) {
                value /= prime;
                ++exponent;
            }
            maximumExponent[prime] = std::max(maximumExponent[prime], exponent);
        }
        if (value > 1) {
            maximumExponent[value] = std::max(maximumExponent[value], 1);
        }
    }

    // Every input denominator divides this global common denominator.
    BigUInt commonDenominator(1);
    std::vector<std::pair<int, int>> primePowers;
    for (int prime = 2; prime <= 1000; ++prime) {
        if (maximumExponent[prime] == 0) {
            continue;
        }
        primePowers.push_back({prime, maximumExponent[prime]});
        for (int exponent = 0; exponent < maximumExponent[prime]; ++exponent) {
            commonDenominator *= static_cast<std::uint32_t>(prime);
        }
    }

    std::vector<std::vector<Edge>> graph(n);
    for (const RawEdge& raw : rawEdges) {
        BigUInt scaledWeight = commonDenominator;
        const std::uint32_t remainder =
            scaledWeight.divideSmall(static_cast<std::uint32_t>(raw.denominator));
        assert(remainder == 0);
        scaledWeight *= static_cast<std::uint32_t>(raw.numerator);

        graph[raw.u].push_back({raw.v, scaledWeight});
        graph[raw.v].push_back({raw.u, std::move(scaledWeight)});
    }

    std::vector<BigUInt> distance(n);
    std::vector<bool> reached(n, false);
    std::priority_queue<State, std::vector<State>, StateGreater> queue;

    reached[0] = true;
    distance[0] = BigUInt(0);
    queue.push({BigUInt(0), 0});

    while (!queue.empty()) {
        State current = queue.top();
        queue.pop();

        if (!reached[current.vertex] || current.distance != distance[current.vertex]) {
            continue;
        }

        for (const Edge& edge : graph[current.vertex]) {
            BigUInt nextDistance = current.distance;
            nextDistance += edge.weight;

            if (!reached[edge.to] || nextDistance < distance[edge.to]) {
                reached[edge.to] = true;
                distance[edge.to] = nextDistance;
                queue.push({std::move(nextDistance), edge.to});
            }
        }
    }

    for (int vertex = 1; vertex < n; ++vertex) {
        BigUInt numerator = distance[vertex];
        BigUInt denominator = commonDenominator;

        // Since denominator's complete prime factorization is known, reduce the
        // fraction without implementing arbitrary-precision gcd or division.
        for (const auto& [prime, exponent] : primePowers) {
            for (int count = 0; count < exponent; ++count) {
                if (numerator.modSmall(static_cast<std::uint32_t>(prime)) != 0) {
                    break;
                }
                const std::uint32_t numeratorRemainder =
                    numerator.divideSmall(static_cast<std::uint32_t>(prime));
                const std::uint32_t denominatorRemainder =
                    denominator.divideSmall(static_cast<std::uint32_t>(prime));
                assert(numeratorRemainder == 0 && denominatorRemainder == 0);
            }
        }

        std::cout << numerator.toString() << ' ' << denominator.toString() << '\n';
    }

    return 0;
}