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

• 問題: No.3669 误差绝不允许
• ユーザー: harurun
• 提出日時: 2026-08-07 03:41:46
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0)
• 結果: AC
• 実行時間: 419 ms / 3,000 ms
• コード長: 4,671 bytes
• コンパイル時間: 5,013 ms
• コンパイル使用メモリ: 448,464 KB
• 実行使用メモリ: 31,904 KB
• 最終ジャッジ日時: 2026-09-04 22:10:11
• 合計ジャッジ時間: 12,723 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

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

ソースコード

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

#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::cpp_int;
using boost::multiprecision::integer_modulus;

namespace {

constexpr int MAX_AB = 300;

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

struct Edge {
    int to;
    cpp_int weight;
};

struct State {
    cpp_int distance;
    int vertex;
};

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

}  // namespace

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);

    // maximumExponent[p] is the largest exponent of p occurring in any b_i.
    std::vector<int> maximumExponent(MAX_AB + 1, 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 b_i divides this common denominator.
    cpp_int commonDenominator = 1;
    std::vector<std::pair<int, int>> primePowers;

    for (int prime = 2; prime <= MAX_AB; ++prime) {
        if (maximumExponent[prime] == 0) {
            continue;
        }

        primePowers.push_back({prime, maximumExponent[prime]});
        for (int exponent = 0;
             exponent < maximumExponent[prime];
             ++exponent) {
            commonDenominator *= prime;
        }
    }

    std::vector<std::vector<Edge>> graph(n);

    for (const RawEdge& raw : rawEdges) {
        cpp_int scaledWeight = commonDenominator;
        scaledWeight /= raw.denominator;
        scaledWeight *= raw.numerator;

        // One copy and one move are necessary because the graph is undirected.
        graph[raw.u].push_back({raw.v, scaledWeight});
        graph[raw.v].push_back({raw.u, std::move(scaledWeight)});
    }

    std::vector<cpp_int> distance(n);
    std::vector<char> reached(n, false);

    std::priority_queue<State, std::vector<State>, StateGreater> queue;

    reached[0] = true;
    distance[0] = 0;
    queue.push({cpp_int(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]) {
            // Evaluate the arbitrary-precision addition exactly once.
            cpp_int nextDistance = current.distance + 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});
            }
        }
    }

    // The official output limit is approximately 8 MiB, so buffering the
    // complete answer avoids tens of thousands of formatted stream writes.
    std::string output;
    output.reserve(8U * 1024U * 1024U);

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

        // The complete prime factorization of the denominator is already
        // known. Reduce by small primes instead of running a general cpp_int
        // Euclidean gcd for every output vertex.
        for (const auto& [prime, exponent] : primePowers) {
            for (int count = 0; count < exponent; ++count) {
                if (integer_modulus(numerator, prime) != 0) {
                    break;
                }
                numerator /= prime;
                denominator /= prime;
            }
        }

        output += numerator.str();
        output.push_back(' ');
        output += denominator.str();
        output.push_back('\n');
    }

    std::cout << output;
    return 0;
}