#1175575 (Java) No.3669 误差绝不允许

• 問題: No.3669 误差绝不允许
• ユーザー: harurun
• 提出日時: 2026-08-07 04:24:38
• 言語: Java (openjdk 26.0.2.1)
• 結果: AC
• 実行時間: 1,486 ms / 3,000 ms
• コード長: 7,475 bytes
• コンパイル時間: 2,422 ms
• コンパイル使用メモリ: 87,492 KB
• 実行使用メモリ: 91,360 KB
• 最終ジャッジ日時: 2026-09-04 22:11:28
• 合計ジャッジ時間: 24,044 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_1

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

ソースコード

import java.io.BufferedInputStream;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    private static final int MAX_AB = 300;

    private static class RawEdge {
        final int u;
        final int v;
        final int numerator;
        final int denominator;

        RawEdge(int u, int v, int numerator, int denominator) {
            this.u = u;
            this.v = v;
            this.numerator = numerator;
            this.denominator = denominator;
        }
    }

    private static class Edge {
        final int to;
        final BigInteger weight;

        Edge(int to, BigInteger weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    private static class State implements Comparable<State> {
        final BigInteger distance;
        final int vertex;

        State(BigInteger distance, int vertex) {
            this.distance = distance;
            this.vertex = vertex;
        }

        @Override
        public int compareTo(State other) {
            int result = distance.compareTo(other.distance);

            if (result != 0) {
                return result;
            }

            return Integer.compare(vertex, other.vertex);
        }
    }

    private static class FastScanner {
        private final BufferedInputStream input =
            new BufferedInputStream(System.in);

        private final byte[] buffer = new byte[1 << 16];
        private int position = 0;
        private int length = 0;

        private int read() throws IOException {
            if (position >= length) {
                length = input.read(buffer);
                position = 0;

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

            return buffer[position++];
        }

        int nextInt() throws IOException {
            int c;

            do {
                c = read();
            } while (c <= ' ' && 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(String[] args) throws Exception {
        FastScanner scanner = new FastScanner();

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

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

        // maximumExponent[p]は、いずれかのb_iに現れる
        // 素数pの指数の最大値。
        int[] maximumExponent = new int[MAX_AB + 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;
        List<int[]> primePowers = new ArrayList<>();

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

            if (exponent == 0) {
                continue;
            }

            primePowers.add(new int[]{prime, exponent});

            BigInteger primeValue = BigInteger.valueOf(prime);

            for (int count = 0; count < exponent; ++count) {
                commonDenominator =
                    commonDenominator.multiply(primeValue);
            }
        }

        @SuppressWarnings("unchecked")
        List<Edge>[] graph = new ArrayList[n];

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

        for (RawEdge raw : rawEdges) {
            BigInteger scaledWeight = commonDenominator
                .divide(BigInteger.valueOf(raw.denominator))
                .multiply(BigInteger.valueOf(raw.numerator));

            // BigIntegerは不変オブジェクトなので、
            // 同じインスタンスを両方の辺で共有してよい。
            graph[raw.u].add(new Edge(raw.v, scaledWeight));
            graph[raw.v].add(new Edge(raw.u, scaledWeight));
        }

        BigInteger[] distance = new BigInteger[n];
        boolean[] reached = new boolean[n];

        PriorityQueue<State> queue = new PriorityQueue<>();

        reached[0] = true;
        distance[0] = BigInteger.ZERO;
        queue.add(new State(BigInteger.ZERO, 0));

        while (!queue.isEmpty()) {
            State current = queue.poll();

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

            for (Edge edge : graph[current.vertex]) {
                // 多倍長整数の加算を一度だけ行う。
                BigInteger nextDistance =
                    current.distance.add(edge.weight);

                if (!reached[edge.to]
                        || nextDistance.compareTo(distance[edge.to]) < 0) {
                    reached[edge.to] = true;
                    distance[edge.to] = nextDistance;
                    queue.add(new State(nextDistance, edge.to));
                }
            }
        }

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

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

            // 分母の素因数分解は既知なので、
            // 各小さい素数で割れるだけ約分する。
            for (int[] primePower : primePowers) {
                int prime = primePower[0];
                int exponent = primePower[1];

                BigInteger primeValue =
                    BigInteger.valueOf(prime);

                for (int count = 0; count < exponent; ++count) {
                    if (numerator
                            .remainder(primeValue)
                            .signum() != 0) {
                        break;
                    }

                    numerator = numerator.divide(primeValue);
                    denominator = denominator.divide(primeValue);
                }
            }

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

        BufferedWriter writer =
            new BufferedWriter(new OutputStreamWriter(System.out));

        writer.write(output.toString());
        writer.flush();
    }
}