#1175578 (D) No.3669 误差绝不允许

• 問題: No.3669 误差绝不允许
• ユーザー: harurun
• 提出日時: 2026-08-07 04:30:27
• 言語: D (dmd 2.113.0)
• 結果: TLE
• 実行時間: -
• コード長: 6,673 bytes
• コンパイル時間: 2,693 ms
• コンパイル使用メモリ: 117,504 KB
• 実行使用メモリ: 29,508 KB
• 最終ジャッジ日時: 2026-09-04 22:12:04
• 合計ジャッジ時間: 8,425 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 2
other	AC * 10 TLE * 1 -- * 19

ソースコード

import core.stdc.stdio : fread, stdin;
import std.array : appender;
import std.bigint : BigInt;
import std.conv : to;
import std.stdio : stdout;

enum MAX_AB = 300;

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

struct Edge
{
    int to;
    BigInt weight;
}

struct State
{
    BigInt distance;
    int vertex;
}

struct PrimePower
{
    int prime;
    int exponent;
}

struct FastScanner
{
private:
    ubyte[1 << 16] buffer;
    size_t position;
    size_t length;

    int readByte()
    {
        if (position >= length)
        {
            length = fread(
                buffer.ptr,
                1,
                buffer.length,
                stdin
            );
            position = 0;

            if (length == 0)
            {
                return -1;
            }
        }

        return buffer[position++];
    }

public:
    int nextInt()
    {
        int c;

        do
        {
            c = readByte();
        }
        while (c <= ' ' && c != -1);

        int sign = 1;

        if (c == '-')
        {
            sign = -1;
            c = readByte();
        }

        int value = 0;

        while ('0' <= c && c <= '9')
        {
            value = value * 10 + c - '0';
            c = readByte();
        }

        return value * sign;
    }
}

struct MinHeap
{
private:
    State[] heap;

    static bool less(ref State lhs, ref State rhs)
    {
        if (lhs.distance != rhs.distance)
        {
            return lhs.distance < rhs.distance;
        }

        return lhs.vertex < rhs.vertex;
    }

public:
    @property bool empty() const
    {
        return heap.length == 0;
    }

    void push(State state)
    {
        size_t index = heap.length;
        heap ~= state;

        while (index > 0)
        {
            size_t parent = (index - 1) / 2;

            if (!less(state, heap[parent]))
            {
                break;
            }

            heap[index] = heap[parent];
            index = parent;
        }

        heap[index] = state;
    }

    State pop()
    {
        State result = heap[0];
        State last = heap[$ - 1];

        heap.length = heap.length - 1;

        if (heap.length == 0)
        {
            return result;
        }

        size_t index = 0;

        while (true)
        {
            size_t left = index * 2 + 1;

            if (left >= heap.length)
            {
                break;
            }

            size_t right = left + 1;
            size_t child = left;

            if (right < heap.length &&
                less(heap[right], heap[left]))
            {
                child = right;
            }

            if (!less(heap[child], last))
            {
                break;
            }

            heap[index] = heap[child];
            index = child;
        }

        heap[index] = last;

        return result;
    }
}

void main()
{
    FastScanner scanner;

    int n = scanner.nextInt();
    int m = scanner.nextInt();

    RawEdge[] rawEdges = new RawEdge[m];

    // maximumExponent[p]は、いずれかのb_iに現れる
    // 素数pの指数の最大値。
    int[] maximumExponent = new int[MAX_AB + 1];

    foreach (i; 0 .. m)
    {
        int u = scanner.nextInt() - 1;
        int v = scanner.nextInt() - 1;
        int a = scanner.nextInt();
        int b = scanner.nextInt();

        rawEdges[i] = RawEdge(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;
            }

            if (exponent > maximumExponent[prime])
            {
                maximumExponent[prime] = exponent;
            }
        }

        if (value > 1 && maximumExponent[value] < 1)
        {
            maximumExponent[value] = 1;
        }
    }

    // すべてのb_iを割り切る共通分母を構築する。
    BigInt commonDenominator = BigInt(1);
    PrimePower[] primePowers;

    foreach (prime; 2 .. MAX_AB + 1)
    {
        int exponent = maximumExponent[prime];

        if (exponent == 0)
        {
            continue;
        }

        primePowers ~= PrimePower(prime, exponent);

        foreach (_; 0 .. exponent)
        {
            commonDenominator *= prime;
        }
    }

    Edge[][] graph = new Edge[][](n);

    foreach (ref raw; rawEdges)
    {
        BigInt scaledWeight = commonDenominator;
        scaledWeight /= raw.denominator;
        scaledWeight *= raw.numerator;

        // BigIntは値として扱えるため、同じ重みを両方向に格納する。
        graph[raw.u] ~= Edge(raw.v, scaledWeight);
        graph[raw.v] ~= Edge(raw.u, scaledWeight);
    }

    BigInt[] distance = new BigInt[n];
    bool[] reached = new bool[n];

    MinHeap queue;

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

    queue.push(State(BigInt(0), 0));

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

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

        foreach (ref edge; graph[current.vertex])
        {
            // 任意精度整数の加算を一度だけ行う。
            BigInt nextDistance =
                current.distance + edge.weight;

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

                queue.push(State(nextDistance, edge.to));
            }
        }
    }

    auto output = appender!string();
    output.reserve(8U * 1024U * 1024U);

    foreach (vertex; 1 .. n)
    {
        BigInt numerator = distance[vertex];
        BigInt denominator = commonDenominator;

        // 分母の素因数分解は既知なので、
        // 各素数で割れる回数だけ約分する。
        foreach (ref primePower; primePowers)
        {
            foreach (_; 0 .. primePower.exponent)
            {
                if (numerator % primePower.prime != 0)
                {
                    break;
                }

                numerator /= primePower.prime;
                denominator /= primePower.prime;
            }
        }

        output.put(to!string(numerator));
        output.put(' ');
        output.put(to!string(denominator));
        output.put('\n');
    }

    stdout.write(output.data);
}