#1182692 (PyPy3) No.3669 误差绝不允许

• 問題: No.3669 误差绝不允许
• ユーザー: 回転
• 提出日時: 2026-09-04 23:51:08
• 言語: PyPy3 (7.3.23)
• 結果: AC
• 実行時間: 1,194 ms / 3,000 ms
• コード長: 5,860 bytes
• コンパイル時間: 466 ms
• コンパイル使用メモリ: 96,072 KB
• 実行使用メモリ: 126,540 KB
• 最終ジャッジ日時: 2026-09-04 23:51:27
• 合計ジャッジ時間: 16,396 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge1_0

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

ソースコード

import math

class Fraction:
    __slots__ = ('num', 'den')

    def __init__(self, numerator, denominator=1):
        if type(numerator) is Fraction and denominator == 1:
            self.num = numerator.num
            self.den = numerator.den
            return

        if denominator == 0:
            raise ZeroDivisionError("Fraction denominator cannot be zero")
        
        # math.gcd はC実装のため非常に高速
        g = math.gcd(numerator, denominator)
        if denominator < 0:
            g = -g
        
        self.num = numerator // g
        self.den = denominator // g

    @property
    def numerator(self):
        return self.num

    @property
    def denominator(self):
        return self.den

    def as_integer_ratio(self):
        """分子と分母のペアをタプルで返す"""
        return (self.num, self.den)

    def __add__(self, other):
        if type(other) is int:
            return Fraction(self.num + other * self.den, self.den)
        elif type(other) is Fraction:
            return Fraction(self.num * other.den + other.num * self.den, self.den * other.den)
        return NotImplemented

    def __radd__(self, other):
        return self.__add__(other)

    def __sub__(self, other):
        if type(other) is int:
            return Fraction(self.num - other * self.den, self.den)
        elif type(other) is Fraction:
            return Fraction(self.num * other.den - other.num * self.den, self.den * other.den)
        return NotImplemented

    def __rsub__(self, other):
        if type(other) is int:
            return Fraction(other * self.den - self.num, self.den)
        return NotImplemented

    def __mul__(self, other):
        if type(other) is int:
            return Fraction(self.num * other, self.den)
        elif type(other) is Fraction:
            return Fraction(self.num * other.num, self.den * other.den)
        return NotImplemented

    def __rmul__(self, other):
        return self.__mul__(other)

    def __truediv__(self, other):
        if type(other) is int:
            return Fraction(self.num, self.den * other)
        elif type(other) is Fraction:
            return Fraction(self.num * other.den, self.den * other.num)
        return NotImplemented

    def __rtruediv__(self, other):
        if type(other) is int:
            return Fraction(other * self.den, self.num)
        return NotImplemented
    
    def __floordiv__(self, other):
        return int(self.__truediv__(other))
    
    def __rfloordiv__(self, other):
        return int(self.__rtruediv__(other))
        
    def __mod__(self, other):
        div = self // other
        return self - other * div
        
    def __rmod__(self, other):
        div = other // self
        return other - self * div

    def __pow__(self, power):
        if type(power) is int:
            if power >= 0:
                return Fraction(self.num ** power, self.den ** power)
            else:
                return Fraction(self.den ** -power, self.num ** -power)
        return float(self) ** power

    def __neg__(self):
        return Fraction(-self.num, self.den)

    def __pos__(self):
        return self

    def __abs__(self):
        return Fraction(abs(self.num), self.den)

    def __eq__(self, other):
        if type(other) is int:
            return self.num == other and self.den == 1
        if type(other) is Fraction:
            return self.num == other.num and self.den == other.den
        if type(other) is float:
            return float(self) == other
        return NotImplemented

    def __lt__(self, other):
        if type(other) is int:
            return self.num < other * self.den
        if type(other) is Fraction:
            return self.num * other.den < other.num * self.den
        if type(other) is float:
            return float(self) < other
        return NotImplemented

    def __le__(self, other):
        if type(other) is int:
            return self.num <= other * self.den
        if type(other) is Fraction:
            return self.num * other.den <= other.num * self.den
        if type(other) is float:
            return float(self) <= other
        return NotImplemented

    def __gt__(self, other):
        if type(other) is int:
            return self.num > other * self.den
        if type(other) is Fraction:
            return self.num * other.den > other.num * self.den
        if type(other) is float:
            return float(self) > other
        return NotImplemented

    def __ge__(self, other):
        if type(other) is int:
            return self.num >= other * self.den
        if type(other) is Fraction:
            return self.num * other.den >= other.num * self.den
        if type(other) is float:
            return float(self) >= other
        return NotImplemented

    def __bool__(self):
        return self.num != 0

    def __int__(self):
        return self.num // self.den

    def __float__(self):
        return self.num / self.den

    def __hash__(self):
        return hash((self.num, self.den))

    def __str__(self):
        if self.den == 1:
            return str(self.num)
        return f"{self.num}/{self.den}"

    def __repr__(self):
        return f"Fraction({self.num}, {self.den})"

import heapq
import sys
input = sys.stdin.readline
N,M = list(map(int,input().split()))
edge = [[] for _ in range(N)]
for _ in range(M):
    u,v,a,b = list(map(int,input().split()))
    u -= 1;v -= 1
    edge[u].append((v,Fraction(a,b)))
    edge[v].append((u,Fraction(a,b)))

INF = Fraction(10**7)
visited = [INF] * N
q = [(0,0)]
while(q):
    v,now = heapq.heappop(q)

    if(visited[now] <= v):continue
    visited[now] = v

    for u,d in edge[now]:
        if(visited[u] <= v + d):continue
        heapq.heappush(q, (v + d, u))

for i in range(1,N):
    print(*visited[i].as_integer_ratio())