#1175579 (Go) No.3669 误差绝不允许

• 問題: No.3669 误差绝不允许
• ユーザー: harurun
• 提出日時: 2026-08-07 04:32:16
• 言語: Go (1.27.0)
• 結果: AC
• 実行時間: 582 ms / 3,000 ms
• コード長: 5,288 bytes
• コンパイル時間: 16,042 ms
• コンパイル使用メモリ: 269,832 KB
• 実行使用メモリ: 45,824 KB
• 最終ジャッジ日時: 2026-09-04 22:12:26
• 合計ジャッジ時間: 25,634 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

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

ソースコード

package main

import (
	"bytes"
	"container/heap"
	"io"
	"math/big"
	"os"
)

const MaxAB = 300

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

type Edge struct {
	to     int
	weight *big.Int
}

type State struct {
	distance *big.Int
	vertex   int
}

type PriorityQueue []State

func (pq PriorityQueue) Len() int {
	return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
	comparison := pq[i].distance.Cmp(pq[j].distance)

	if comparison != 0 {
		return comparison < 0
	}

	return pq[i].vertex < pq[j].vertex
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(value interface{}) {
	*pq = append(*pq, value.(State))
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	lastIndex := len(old) - 1
	result := old[lastIndex]

	old[lastIndex] = State{}
	*pq = old[:lastIndex]

	return result
}

type PrimePower struct {
	prime    int
	exponent int
}

type FastScanner struct {
	data  []byte
	index int
}

func NewFastScanner() *FastScanner {
	data, err := io.ReadAll(os.Stdin)
	if err != nil {
		panic(err)
	}

	return &FastScanner{
		data: data,
	}
}

func (scanner *FastScanner) NextInt() int {
	for scanner.index < len(scanner.data) &&
		scanner.data[scanner.index] <= ' ' {
		scanner.index++
	}

	sign := 1

	if scanner.data[scanner.index] == '-' {
		sign = -1
		scanner.index++
	}

	value := 0

	for scanner.index < len(scanner.data) {
		c := scanner.data[scanner.index]

		if c < '0' || c > '9' {
			break
		}

		value = value*10 + int(c-'0')
		scanner.index++
	}

	return value * sign
}

func main() {
	scanner := NewFastScanner()

	n := scanner.NextInt()
	m := scanner.NextInt()

	rawEdges := make([]RawEdge, 0, m)

	// maximumExponent[p]は、いずれかのb_iに現れる
	// 素数pの指数の最大値。
	maximumExponent := make([]int, MaxAB+1)

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

		rawEdges = append(rawEdges, RawEdge{
			u:           u,
			v:           v,
			numerator:   a,
			denominator: b,
		})

		value := b

		for prime := 2; prime*prime <= value; prime++ {
			if value%prime != 0 {
				continue
			}

			exponent := 0

			for value%prime == 0 {
				value /= prime
				exponent++
			}

			if exponent > maximumExponent[prime] {
				maximumExponent[prime] = exponent
			}
		}

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

	// すべてのb_iを割り切る共通分母を構築する。
	commonDenominator := big.NewInt(1)
	primePowers := make([]PrimePower, 0)

	for prime := 2; prime <= MaxAB; prime++ {
		exponent := maximumExponent[prime]

		if exponent == 0 {
			continue
		}

		primePowers = append(primePowers, PrimePower{
			prime:    prime,
			exponent: exponent,
		})

		primeValue := big.NewInt(int64(prime))

		for count := 0; count < exponent; count++ {
			commonDenominator.Mul(
				commonDenominator,
				primeValue,
			)
		}
	}

	graph := make([][]Edge, n)

	for _, raw := range rawEdges {
		scaledWeight := new(big.Int).Set(commonDenominator)

		scaledWeight.Quo(
			scaledWeight,
			big.NewInt(int64(raw.denominator)),
		)

		scaledWeight.Mul(
			scaledWeight,
			big.NewInt(int64(raw.numerator)),
		)

		// scaledWeightは以後変更しないため、
		// 両方向の辺で共有できる。
		graph[raw.u] = append(graph[raw.u], Edge{
			to:     raw.v,
			weight: scaledWeight,
		})

		graph[raw.v] = append(graph[raw.v], Edge{
			to:     raw.u,
			weight: scaledWeight,
		})
	}

	distance := make([]*big.Int, n)
	reached := make([]bool, n)

	queue := &PriorityQueue{}
	heap.Init(queue)

	reached[0] = true
	distance[0] = big.NewInt(0)

	heap.Push(queue, State{
		distance: big.NewInt(0),
		vertex:   0,
	})

	for queue.Len() > 0 {
		current := heap.Pop(queue).(State)

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

		for _, edge := range graph[current.vertex] {
			// 任意精度整数の加算を一度だけ行う。
			nextDistance := new(big.Int).Add(
				current.distance,
				edge.weight,
			)

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

				heap.Push(queue, State{
					distance: nextDistance,
					vertex:   edge.to,
				})
			}
		}
	}

	var output bytes.Buffer
	output.Grow(8 * 1024 * 1024)

	for vertex := 1; vertex < n; vertex++ {
		numerator := new(big.Int).Set(distance[vertex])
		denominator := new(big.Int).Set(commonDenominator)
		remainder := new(big.Int)

		// 分母の素因数分解は既知なので、
		// 各素数で割れる回数だけ約分する。
		for _, primePower := range primePowers {
			primeValue := big.NewInt(int64(primePower.prime))

			for count := 0; count < primePower.exponent; count++ {
				remainder.Mod(numerator, primeValue)

				if remainder.Sign() != 0 {
					break
				}

				numerator.Quo(numerator, primeValue)
				denominator.Quo(denominator, primeValue)
			}
		}

		output.WriteString(numerator.String())
		output.WriteByte(' ')
		output.WriteString(denominator.String())
		output.WriteByte('\n')
	}

	if _, err := os.Stdout.Write(output.Bytes()); err != nil {
		panic(err)
	}
}