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

• 問題: No.3669 误差绝不允许
• ユーザー: tobisatis
• 提出日時: 2026-09-04 23:29:16
• 言語: C# (.NET 10.0.400)
• 結果: AC
• 実行時間: 1,378 ms / 3,000 ms
• コード長: 5,682 bytes
• コンパイル時間: 5,337 ms
• コンパイル使用メモリ: 173,228 KB
• 実行使用メモリ: 262,180 KB
• 最終ジャッジ日時: 2026-09-04 23:29:34
• 合計ジャッジ時間: 16,797 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge1_0

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

コンパイルメッセージ

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

ソースコード

#nullable enable

using System.Numerics;
using T = System.Numerics.BigInteger;

#region
var (_input, _iter) = (Array.Empty<string>(), 0);
T I<T>() where T : IParsable<T>
{
    while (_iter >= _input.Length) (_input, _iter) = (Console.ReadLine()!.Trim().Split(' '), 0);
    return T.Parse(_input[_iter++], null);
}
#endregion

var n = I<int>();
var m = I<int>();
var ez = new (int, int)[m];
var wz = new Rational[m];
for (var i = 0; i < m; i++)
{
    ez[i] = (I<int>() - 1, I<int>() - 1);
    wz[i] = new(I<int>(), I<int>());
}
var g = new StaticGraph(ez, n, false).ToGraph();
var dpz = new decimal[m];
for (var i = 0; i < m; i++) dpz[i] = (decimal)wz[i].P / (decimal)wz[i].Q;
var dz = g.Distances(0, dpz, long.MaxValue).ToArray();
var nns = new Rational[n];
nns[0] = new(0);
for (var i = 1; i < n; i++) nns[i] = new(-1);
Rational S(int v)
{
    if (nns[v] >= new Rational(0)) return nns[v];
    var p = dz[v].PrevV;
    return nns[v] = S(p) + wz[dz[v].PrevE];
}
for (var i = 1; i < n; i++) S(i);
var ans = nns[1..].Select(e => e.P + " " + e.Q).ToArray();
Console.WriteLine(string.Join(Environment.NewLine, ans));

readonly record struct Rational :
IAdditiveIdentity<Rational, Rational>,
IAdditionOperators<Rational, Rational, Rational>,
ISubtractionOperators<Rational, Rational, Rational>,
IUnaryNegationOperators<Rational, Rational>,
IMultiplicativeIdentity<Rational, Rational>,
IMultiplyOperators<Rational, Rational, Rational>,
IDivisionOperators<Rational, Rational, Rational>,
IComparable<Rational>,
IEqualityOperators<Rational, Rational, bool>,
IComparisonOperators<Rational, Rational, bool>
{
    public T P { get; private init; }
    public T Q { get; private init; }
    public Rational(T p, T q)
    {
        if (q == T.Zero) throw new DivideByZeroException();
        if (q < T.Zero) (p, q) = (-p, -q);
        var (x, y) = (T.Abs(p), q);
        while (y > T.Zero) (x, y) = (y, x % y);
        (P, Q) = (p / x, q / x);
    }
    public Rational(T p) { (P, Q) = (p, T.One); }
    public static Rational AdditiveIdentity => new(T.Zero); 
    public static Rational MultiplicativeIdentity => new(T.One);

    public static implicit operator Rational(T i) => new(i);
    public static Rational operator -(Rational r) => new(-r.P, r.Q);
    public static Rational operator +(Rational r1, Rational r2) => new(r1.P * r2.Q + r1.Q * r2.P, r1.Q * r2.Q);
    public static Rational operator -(Rational r1, Rational r2) => new(r1.P * r2.Q - r1.Q * r2.P, r1.Q * r2.Q);
    public static Rational operator *(Rational r1, Rational r2) => new(r1.P * r2.P, r1.Q * r2.Q);
    public static Rational operator /(Rational r1, Rational r2) => new(r1.P * r2.Q, r1.Q * r2.P);
    public static bool operator <(Rational r1, Rational r2) => r1.CompareTo(r2) < 0;
    public static bool operator <=(Rational r1, Rational r2) => r1.CompareTo(r2) <= 0;
    public static bool operator >(Rational r1, Rational r2) => r1.CompareTo(r2) > 0;
    public static bool operator >=(Rational r1, Rational r2) => r1.CompareTo(r2) >= 0;
    public int CompareTo(Rational r) => (P * r.Q).CompareTo(Q * r.P);
}

class StaticGraph
{
    public int N { get; }
    public bool Directed { get; }
    public ReadOnlySpan<(int next, int edgeIndex)> Adjacencies(int of) => _adjacencies.AsSpan()[_starts[of].._starts[of + 1]];
    public ReadOnlySpan<(int Ab, int Ad)> Edges => _edges;

    readonly (int Ab, int Ad)[] _edges;
    readonly (int, int)[] _adjacencies;
    readonly int[] _starts;

    public StaticGraph(IReadOnlyList<(int, int)> edges, int n, bool directed)
    {
        var ez = edges.ToArray();
        var el = ez.Length;
        var m = directed ? el : (el << 1);
        var starts = new int[n + 1];
        for (var i = 0; i < el; i++)
        {
            var (ab, ad) = ez[i];
            starts[ab + 1]++;
            if (!directed) starts[ad + 1]++;
        }
        for (var i = 0; i < n; i++) starts[i + 1] += starts[i];
        var adjacencies = new (int, int)[m];
        var counts = starts.AsSpan().ToArray();
        for (var i = 0; i < el; i++)
        {
            var (ab, ad) = ez[i];
            adjacencies[counts[ab]++] = (ad, i);
            if (!directed) adjacencies[counts[ad]++] = (ab, i);
        }
        N = n;
        Directed = directed;
        _adjacencies = adjacencies;
        _edges = ez;
        _starts = starts;
    }
}

class Graph { public required StaticGraph StaticGraph { get; init; } }

static class GraphBaseExtensions
{
    public static Graph ToGraph(this StaticGraph g) => new(){ StaticGraph = g };

    public static Span<(T Distance, int PrevV, int PrevE)> Distances<T>(
        this Graph graph,
        int start,
        IReadOnlyList<T> distances,
        T infinity
    )
        where T :
        IComparable<T>,
        IAdditiveIdentity<T, T>,
        IAdditionOperators<T, T, T>
    {
        var g = graph.StaticGraph;
        var res = new (T, int, int)[g.N].AsSpan();
        for (var i = 0; i < res.Length; i++) res[i] = (infinity, -1, -1);
        var determined = new bool[g.N].AsSpan();
        var q = new PriorityQueue<int, T>();
        q.Enqueue(start, res[start].Item1 = T.AdditiveIdentity);
        while (q.Count > 0)
        {
            var v = q.Dequeue();
            if (determined[v]) continue;
            determined[v] = true;
            var cd = res[v].Item1;
            var adjacencies = g.Adjacencies(v);
            foreach (var (next, ei) in adjacencies)
            {
                var d = cd + distances[ei];
                if (res[next].Item1.CompareTo(d) <= 0) continue;
                res[next] = (d, v, ei);
                q.Enqueue(next, d);
            }
        }
        return res;
    }

}