#1175577 (C#) No.3669 误差绝不允许

• 問題: No.3669 误差绝不允许
• ユーザー: harurun
• 提出日時: 2026-08-07 04:28:10
• 言語: C# (.NET 10.0.400)
• 結果: AC
• 実行時間: 849 ms / 3,000 ms
• コード長: 8,921 bytes
• コンパイル時間: 7,875 ms
• コンパイル使用メモリ: 174,296 KB
• 実行使用メモリ: 252,764 KB
• 最終ジャッジ日時: 2026-09-04 22:12:00
• 合計ジャッジ時間: 21,001 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

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

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (90 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

using System;
using System.Collections.Generic;
using System.IO;
using System.Numerics;
using System.Text;

public class Program
{
    private const int MaxAb = 300;

    private struct RawEdge
    {
        public int U;
        public int V;
        public int Numerator;
        public int Denominator;

        public RawEdge(int u, int v, int numerator, int denominator)
        {
            U = u;
            V = v;
            Numerator = numerator;
            Denominator = denominator;
        }
    }

    private struct Edge
    {
        public int To;
        public BigInteger Weight;

        public Edge(int to, BigInteger weight)
        {
            To = to;
            Weight = weight;
        }
    }

    private struct State
    {
        public BigInteger Distance;
        public int Vertex;

        public State(BigInteger distance, int vertex)
        {
            Distance = distance;
            Vertex = vertex;
        }
    }

    private struct PrimePower
    {
        public int Prime;
        public int Exponent;

        public PrimePower(int prime, int exponent)
        {
            Prime = prime;
            Exponent = exponent;
        }
    }

    private sealed class MinHeap
    {
        private readonly List<State> heap = new List<State>();

        public int Count
        {
            get { return heap.Count; }
        }

        private static bool Less(State lhs, State rhs)
        {
            int comparison = lhs.Distance.CompareTo(rhs.Distance);

            if (comparison != 0)
            {
                return comparison < 0;
            }

            return lhs.Vertex < rhs.Vertex;
        }

        public void Push(State state)
        {
            int index = heap.Count;
            heap.Add(state);

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

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

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

            heap[index] = state;
        }

        public State Pop()
        {
            State result = heap[0];
            int lastIndex = heap.Count - 1;
            State last = heap[lastIndex];

            heap.RemoveAt(lastIndex);

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

            int index = 0;

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

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

                int right = left + 1;
                int child = left;

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

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

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

            heap[index] = last;
            return result;
        }
    }

    private sealed class FastScanner
    {
        private readonly Stream input = Console.OpenStandardInput();
        private readonly byte[] buffer = new byte[1 << 16];

        private int length;
        private int position;

        private int Read()
        {
            if (position >= length)
            {
                length = input.Read(buffer, 0, buffer.Length);
                position = 0;

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

            return buffer[position++];
        }

        public int NextInt()
        {
            int c;

            do
            {
                c = Read();
            }
            while (c <= 32 && c != -1);

            int sign = 1;

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

            int value = 0;

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

            return value * sign;
        }
    }

    public static void Main()
    {
        var scanner = new FastScanner();

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

        var rawEdges = new List<RawEdge>(m);

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

        for (int i = 0; i < m; ++i)
        {
            int u = scanner.NextInt() - 1;
            int v = scanner.NextInt() - 1;
            int a = scanner.NextInt();
            int b = scanner.NextInt();

            rawEdges.Add(new 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;
                }

                maximumExponent[prime] =
                    Math.Max(maximumExponent[prime], exponent);
            }

            if (value > 1)
            {
                maximumExponent[value] =
                    Math.Max(maximumExponent[value], 1);
            }
        }

        // すべてのb_iを割り切る共通分母を構築する。
        BigInteger commonDenominator = BigInteger.One;
        var primePowers = new List<PrimePower>();

        for (int prime = 2; prime <= MaxAb; ++prime)
        {
            int exponent = maximumExponent[prime];

            if (exponent == 0)
            {
                continue;
            }

            primePowers.Add(new PrimePower(prime, exponent));

            for (int count = 0; count < exponent; ++count)
            {
                commonDenominator *= prime;
            }
        }

        var graph = new List<Edge>[n];

        for (int vertex = 0; vertex < n; ++vertex)
        {
            graph[vertex] = new List<Edge>();
        }

        foreach (RawEdge raw in rawEdges)
        {
            BigInteger scaledWeight =
                commonDenominator / raw.Denominator * raw.Numerator;

            // BigIntegerは不変の値型なので、同じ値を両方向で使用できる。
            graph[raw.U].Add(new Edge(raw.V, scaledWeight));
            graph[raw.V].Add(new Edge(raw.U, scaledWeight));
        }

        var distance = new BigInteger[n];
        var reached = new bool[n];
        var queue = new MinHeap();

        reached[0] = true;
        distance[0] = BigInteger.Zero;

        queue.Push(new State(BigInteger.Zero, 0));

        while (queue.Count > 0)
        {
            State current = queue.Pop();

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

            foreach (Edge edge in graph[current.Vertex])
            {
                // 任意精度整数の加算を一度だけ行う。
                BigInteger nextDistance =
                    current.Distance + edge.Weight;

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

                    queue.Push(new State(nextDistance, edge.To));
                }
            }
        }

        var output = new StringBuilder(8 * 1024 * 1024);

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

            // 分母の素因数分解は既知なので、
            // 各素数で割れる回数だけ約分する。
            foreach (PrimePower primePower in primePowers)
            {
                int prime = primePower.Prime;
                int exponent = primePower.Exponent;

                for (int count = 0; count < exponent; ++count)
                {
                    if (numerator % prime != BigInteger.Zero)
                    {
                        break;
                    }

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

            output.Append(numerator);
            output.Append(' ');
            output.Append(denominator);
            output.Append('\n');
        }

        using (var writer = new StreamWriter(
            Console.OpenStandardOutput(),
            new UTF8Encoding(false),
            1 << 16))
        {
            writer.Write(output);
        }
    }
}