提出 #23635585

---

ソースコード 拡げる

using AtCoder;
using AtCoder.Internal;
using Kzrnm.Competitive;
using Kzrnm.Competitive.IO;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.Immutable;
using System.Diagnostics;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using static Kzrnm.Competitive.Global;
using static System.Math;
partial class Program
{
    string YesNo(bool b) => b ? "Yes" : "No";
    const bool __ManyTestCases = false;
    [MethodImpl(MethodImplOptions.AggressiveOptimization)]
    private object Calc()
    {
        int N = cr;
        int M = cr;
        var gb = new WGraphBuilder<long, int, LongOperator>(N, false);
        for (int i = 0; i < M; i++)
        {
            int a = cr.Int0;
            int b = cr.Int0;
            int c = cr.Int0;
            long d = cr.Int;
            gb.Add(a, b, d, c);
        }
        var graphObj = gb.ToGraph();
        if (graphObj.ShortestPathBFS(0)[^1] == uint.MaxValue) return -1;
        var graph = graphObj.AsArray();

        var colors = new Dictionary<int, long>[N];
        for (int i = 0; i < graph.Length; i++)
        {
            var cd = colors[i] = new Dictionary<int, long>();
            foreach (var e in graph[i].Children)
                cd[e.Data] = cd.Get(e.Data) + e.Value;
        }
        var cls = NewArray(N, () => new Dictionary<int, long>());
        var lens = new long[N].Fill(long.MaxValue / 2);
        lens[0] = 0;
        var used = new bool[N];
        var pq = new PriorityQueueDijkstra<long, LongOperator>(N);
        pq.Enqueue(0, 0);
        const long INF = long.MaxValue / 3;
        while (pq.TryDequeue(out var len, out var ix))
        {
            if (len > lens[ix]) continue;
            foreach (var e in graph[ix].Children)
            {
                var to = e.To;
                var color = e.Data;
                var cost = e.Value;
                cls[to][color] = Min(cls[to].GetValueOrDefault(color, INF), len);

                if (lens[to].UpdateMin(
                    Min(cls[ix].GetValueOrDefault(color, len) + colors[ix][color] - cost, len + cost)))
                    pq.Enqueue(lens[to], to);
            }
        }
        return lens[^1];
    }

}
#region Expanded by https://github.com/naminodarie/SourceExpander
//LICENSE:
//https://github.com/naminodarie/Kzrnm.Competitive/blob/master/LICENSE
//https://github.com/naminodarie/Kzrnm.Competitive/blob/master/3rd-party%20Licenses.txt
#pragma warning disable
namespace AtCoder.Internal{public class CSR<TEdge>:IEnumerable<(int from,TEdge edge)>{public readonly int[]Start;public readonly TEdge[]EList;public CSR(int n,ICollection<(int from,TEdge e)>edges){Start=new int[n+1];EList=new TEdge[edges.Count];foreach(var(from,_)in edges){Start[from+1]++;}for(int i=1;i<=n;i++){Start[i]+=Start[i-1];}var counter=(int[])Start.Clone();foreach(var(from,e)in edges){EList[counter[from]++]=e;}}public Enumerator GetEnumerator()=>new Enumerator(this);IEnumerator<(int from,TEdge edge)>IEnumerable<(int from,TEdge edge)>.GetEnumerator()=>GetEnumerator();IEnumerator IEnumerable.GetEnumerator()=>GetEnumerator();public struct Enumerator:IEnumerator<(int from,TEdge edge)>{public Enumerator(CSR<TEdge>g){_g=g;index=-1;start=0;}private CSR<TEdge>_g;private int index;private int start;public(int from,TEdge edge)Current=>(start,_g.EList[index]);object IEnumerator.Current=>Current;public bool MoveNext(){if( ++index<_g.Start[start+1])return true;return MoveNextStart();}private bool MoveNextStart(){for( ++start;start+1<_g.Start.Length;++start)if(index<_g.Start[start+1])return true;return false;}public void Reset(){index=-1;start=0;}void IDisposable.Dispose(){}}}}
namespace AtCoder.Internal{public interface IPriorityQueueOp<T>{int Count{get;}T Peek{get;}void Enqueue(T value);T Dequeue();bool TryDequeue(out T result);void Clear();}}
namespace AtCoder.Internal{public class SimpleList<T>:IList<T>,IReadOnlyList<T>{private T[]data;private const int DefaultCapacity=2;public SimpleList(){data=new T[DefaultCapacity];}public SimpleList(int capacity){data=new T[Math.Max(capacity,DefaultCapacity)];}public SimpleList(IEnumerable<T>collection){if(collection is ICollection<T>col){data=new T[col.Count];col.CopyTo(data,0);Count=col.Count;}else{data=new T[DefaultCapacity];foreach(var item in collection)Add(item);}}public Memory<T>AsMemory()=>new Memory<T>(data,0,Count);public Span<T>AsSpan()=>new Span<T>(data,0,Count);public ref T this[int index]{[MethodImpl(MethodImplOptions.AggressiveInlining)]get{if((uint)index>=(uint)Count)ThrowIndexOutOfRangeException();return ref data[index];}}public int Count{get;private set;}public void Add(T item){if((uint)Count>=(uint)data.Length)Array.Resize(ref data,data.Length<<1);data[Count++]=item;}public void RemoveLast(){if( --Count<0)ThrowIndexOutOfRangeException();}public SimpleList<T>Reverse(){Array.Reverse(data,0,Count);return this;}public SimpleList<T>Reverse(int index,int count){Array.Reverse(data,index,count);return this;}public SimpleList<T>Sort(){Array.Sort(data,0,Count);return this;}public SimpleList<T>Sort(IComparer<T>comparer){Array.Sort(data,0,Count,comparer);return this;}public SimpleList<T>Sort(int index,int count,IComparer<T>comparer){Array.Sort(data,index,count,comparer);return this;}public void Clear()=>Count=0;public bool Contains(T item)=>IndexOf(item)>=0;public int IndexOf(T item)=>Array.IndexOf(data,item,0,Count);public void CopyTo(T[]array,int arrayIndex)=>Array.Copy(data,0,array,arrayIndex,Count);public T[]ToArray()=>AsSpan().ToArray();bool ICollection<T>.IsReadOnly=>false;T IList<T>.this[int index]{get=>data[index];set=>data[index]=value;}T IReadOnlyList<T>.this[int index]{get=>data[index];}void IList<T>.Insert(int index,T item)=>throw new NotSupportedException();bool ICollection<T>.Remove(T item)=>throw new NotSupportedException();void IList<T>.RemoveAt(int index)=>throw new NotSupportedException();IEnumerator IEnumerable.GetEnumerator()=>((IEnumerable<T>)this).GetEnumerator();IEnumerator<T>IEnumerable<T>.GetEnumerator(){for(int i=0;i<Count;i++)yield return data[i];}public Span<T>.Enumerator GetEnumerator()=>AsSpan().GetEnumerator();private static void ThrowIndexOutOfRangeException()=>throw new IndexOutOfRangeException();}}
namespace AtCoder{public interface IAdditionOperator<T>{T Add(T x,T y);T Subtract(T x,T y);}public interface IMultiplicationOperator<T>{T Multiply(T x,T y);T MultiplyIdentity{get;}}public interface IDivisionOperator<T>:IMultiplicationOperator<T>{T Divide(T x,T y);T Modulo(T x,T y);}public interface IUnaryNumOperator<T>{T Minus(T x);T Increment(T x);T Decrement(T x);}public interface IArithmeticOperator<T>:IAdditionOperator<T>,IMultiplicationOperator<T>,IDivisionOperator<T>,IUnaryNumOperator<T>{}public interface ICompareOperator<T>:IComparer<T>{bool GreaterThan(T x,T y);bool GreaterThanOrEqual(T x,T y);bool LessThan(T x,T y);bool LessThanOrEqual(T x,T y);}public interface INumOperator<T>:IArithmeticOperator<T>,ICompareOperator<T>{T MinValue{get;}T MaxValue{get;}}public interface IShiftOperator<T>{T LeftShift(T x,int y);T RightShift(T x,int y);}}
namespace AtCoder{using static MethodImplOptions;public readonly struct LongOperator:INumOperator<long>,IShiftOperator<long>{public long MinValue=>long.MinValue;public long MaxValue=>long.MaxValue;public long MultiplyIdentity=>1L;[MethodImpl(AggressiveInlining)]public long Add(long x,long y)=>x+y;[MethodImpl(AggressiveInlining)]public long Subtract(long x,long y)=>x-y;[MethodImpl(AggressiveInlining)]public long Multiply(long x,long y)=>x*y;[MethodImpl(AggressiveInlining)]public long Divide(long x,long y)=>x/y;[MethodImpl(AggressiveInlining)]public long Modulo(long x,long y)=>x%y;[MethodImpl(AggressiveInlining)]public long Minus(long x)=>-x;[MethodImpl(AggressiveInlining)]public long Increment(long x)=> ++x;[MethodImpl(AggressiveInlining)]public long Decrement(long x)=> --x;[MethodImpl(AggressiveInlining)]public bool GreaterThan(long x,long y)=>x>y;[MethodImpl(AggressiveInlining)]public bool GreaterThanOrEqual(long x,long y)=>x>=y;[MethodImpl(AggressiveInlining)]public bool LessThan(long x,long y)=>x<y;[MethodImpl(AggressiveInlining)]public bool LessThanOrEqual(long x,long y)=>x<=y;[MethodImpl(AggressiveInlining)]public int Compare(long x,long y)=>x.CompareTo(y);[MethodImpl(AggressiveInlining)]public long LeftShift(long x,int y)=>x<<y;[MethodImpl(AggressiveInlining)]public long RightShift(long x,int y)=>x>>y;}}
namespace Kzrnm.Competitive.IO{public partial class ConsoleWriter:IDisposable{private const int DefaultBufferSize=1<<12;public StreamWriter StreamWriter{get;}public ConsoleWriter():this(Console.OpenStandardOutput(),Console.OutputEncoding,DefaultBufferSize){}public ConsoleWriter(Stream output,Encoding encoding):this(output,encoding,DefaultBufferSize){}public ConsoleWriter(Stream output,Encoding encoding,int bufferSize){StreamWriter=new StreamWriter(output,encoding,bufferSize);}public void Flush()=>StreamWriter.Flush();public ConsoleWriter WriteLine(){StreamWriter.WriteLine();return this;}public ConsoleWriter WriteLine<T>(T obj){StreamWriter.WriteLine(obj.ToString());return this;}public ConsoleWriter WriteLineJoin<T>(IEnumerable<T>col)=>WriteMany(' ',col);public ConsoleWriter WriteLineJoin<T1,T2>((T1,T2)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2);public ConsoleWriter WriteLineJoin<T1,T2,T3>((T1,T2,T3)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2,tuple.Item3);public ConsoleWriter WriteLineJoin<T1,T2,T3,T4>((T1,T2,T3,T4)tuple)=>WriteLineJoin(tuple.Item1,tuple.Item2,tuple.Item3,tuple.Item4);public ConsoleWriter WriteLineJoin<TTuple>(TTuple tuple)where TTuple:ITuple{var col=new object[tuple.Length];for(int i=0;i<col.Length;i++)col[i]=tuple[i];return WriteLineJoin(col);}public ConsoleWriter WriteLineJoin(params object[]col)=>WriteMany(' ',col);public ConsoleWriter WriteLineJoin<T1,T2>(T1 v1,T2 v2){StreamWriter.Write(v1.ToString());StreamWriter.Write(' ');StreamWriter.WriteLine(v2.ToString());return this;}public ConsoleWriter WriteLineJoin<T1,T2,T3>(T1 v1,T2 v2,T3 v3){StreamWriter.Write(v1.ToString());StreamWriter.Write(' ');StreamWriter.Write(v2.ToString());StreamWriter.Write(' ');StreamWriter.WriteLine(v3.ToString());return this;}public ConsoleWriter WriteLineJoin<T1,T2,T3,T4>(T1 v1,T2 v2,T3 v3,T4 v4){StreamWriter.Write(v1.ToString());StreamWriter.Write(' ');StreamWriter.Write(v2.ToString());StreamWriter.Write(' ');StreamWriter.Write(v3.ToString());StreamWriter.Write(' ');StreamWriter.WriteLine(v4.ToString());return this;}public ConsoleWriter WriteLines<T>(IEnumerable<T>col)=>WriteMany('\n',col);public ConsoleWriter WriteLineGrid<T>(IEnumerable<IEnumerable<T>>cols){foreach(var col in cols)WriteLineJoin(col);return this;}protected ConsoleWriter WriteMany<T>(char sep,IEnumerable<T>col){var en=col.GetEnumerator();if(!en.MoveNext())goto End;StreamWriter.Write(en.Current.ToString());while(en.MoveNext()){StreamWriter.Write(sep);StreamWriter.Write(en.Current.ToString());}End:StreamWriter.WriteLine();return this;}public void Dispose()=>Flush();}}
namespace Kzrnm.Competitive.IO{public partial class ConsoleWriter{public ConsoleWriter WriteLine(ReadOnlySpan<char>obj){StreamWriter.WriteLine(obj);return this;}public ConsoleWriter WriteLineJoin<T>(Span<T>col)=>WriteMany(' ',(ReadOnlySpan<T>)col);public ConsoleWriter WriteLineJoin<T>(ReadOnlySpan<T>col)=>WriteMany(' ',col);public ConsoleWriter WriteLines<T>(Span<T>col)=>WriteMany('\n',(ReadOnlySpan<T>)col);public ConsoleWriter WriteLines<T>(ReadOnlySpan<T>col)=>WriteMany('\n',col);protected ConsoleWriter WriteMany<T>(char sep,ReadOnlySpan<T>col){var en=col.GetEnumerator();if(!en.MoveNext())return this;StreamWriter.Write(en.Current.ToString());while(en.MoveNext()){StreamWriter.Write(sep);StreamWriter.Write(en.Current.ToString());}StreamWriter.WriteLine();return this;}}}
namespace Kzrnm.Competitive.IO{using static MethodImplOptions;public class PropertyConsoleReader{private const int BufSize=1<<12;private readonly Stream input;private readonly Encoding encoding;internal readonly byte[]buffer=new byte[BufSize];internal int pos=0;internal int len=0;public PropertyConsoleReader():this(Console.OpenStandardInput(),Console.InputEncoding){}public PropertyConsoleReader(Stream input,Encoding encoding){this.input=input;this.encoding=encoding;}[MethodImpl(AggressiveInlining)]protected internal byte Read(){if( ++pos>=len){if((len=input.Read(buffer,0,buffer.Length))<=0){buffer[0]=10;}pos=0;}return buffer[pos];}public int Int{[MethodImpl(AggressiveInlining)]get{int res=0;bool neg=false;byte b;do{b=Read();if(b=='-')neg=true;}while(b<'0');do{res=res*10+(b^'0');b=Read();}while('0'<=b);return neg?-res:res;}}public int Int0{[MethodImpl(AggressiveInlining)]get=>Int-1;}public uint UInt{[MethodImpl(AggressiveInlining)]get=>(uint)ULong;}public uint UInt0{[MethodImpl(AggressiveInlining)]get=>UInt-1;}public long Long{[MethodImpl(AggressiveInlining)]get{long res=0;bool neg=false;byte b;do{b=Read();if(b=='-')neg=true;}while(b<'0');do{res=res*10+(b^'0');b=Read();}while('0'<=b);return neg?-res:res;}}public long Long0{[MethodImpl(AggressiveInlining)]get=>Long-1;}public ulong ULong{[MethodImpl(AggressiveInlining)]get{ulong res=0;byte b;do b=Read();while(b<'0');do{res=res*10+(b^(ulong)'0');b=Read();}while('0'<=b);return res;}}public ulong ULong0{[MethodImpl(AggressiveInlining)]get=>ULong-1;}public string String{[MethodImpl(AggressiveInlining)]get{var sb=new List<byte>();;byte b;do b=Read();while(b<=' ');do{sb.Add(b);b=Read();}while(' '<b);return encoding.GetString(sb.ToArray());}}public string Ascii{[MethodImpl(AggressiveInlining)]get{var sb=new StringBuilder();byte b;do b=Read();while(b<=' ');do{sb.Append((char)b);b=Read();}while(' '<b);return sb.ToString();}}public string Line{[MethodImpl(AggressiveInlining)]get{var sb=new List<byte>();byte b;do b=Read();while(b<=' ');do{sb.Add(b);b=Read();}while(b!='\n'&&b!='\r');return encoding.GetString(sb.ToArray());}}public char Char{[MethodImpl(AggressiveInlining)]get{byte b;do b=Read();while(b<=' ');return(char)b;}}public double Double{[MethodImpl(AggressiveInlining)]get{return double.Parse(Ascii);}}public decimal Decimal{[MethodImpl(AggressiveInlining)]get{return decimal.Parse(Ascii);}}[MethodImpl(AggressiveInlining)]public static implicit operator int(PropertyConsoleReader cr)=>cr.Int;[MethodImpl(AggressiveInlining)]public static implicit operator uint(PropertyConsoleReader cr)=>cr.UInt;[MethodImpl(AggressiveInlining)]public static implicit operator long(PropertyConsoleReader cr)=>cr.Long;[MethodImpl(AggressiveInlining)]public static implicit operator ulong(PropertyConsoleReader cr)=>cr.ULong;[MethodImpl(AggressiveInlining)]public static implicit operator double(PropertyConsoleReader cr)=>cr.Double;[MethodImpl(AggressiveInlining)]public static implicit operator decimal(PropertyConsoleReader cr)=>cr.Decimal;[MethodImpl(AggressiveInlining)]public static implicit operator string(PropertyConsoleReader cr)=>cr.Ascii;}}
namespace Kzrnm.Competitive{using static MethodImplOptions;public class PriorityQueueDijkstra<TKey,TKOp>:IPriorityQueueOp<KeyValuePair<TKey,int>>where TKOp:IComparer<TKey>{private TKey[]keys;private int[]values;private int[]indexes;private readonly TKOp _comparer;public PriorityQueueDijkstra(int capacity):this(capacity,default(TKOp)){}public PriorityQueueDijkstra(int capacity,TKOp comparer){if(comparer==null)throw new ArgumentNullException(nameof(comparer));keys=new TKey[capacity];values=new int[capacity];indexes=new int[capacity].Fill(-1);_comparer=comparer;}public int Count{get;private set;}=0;public KeyValuePair<TKey,int>Peek=>KeyValuePair.Create(keys[0],values[0]);[MethodImpl(AggressiveInlining)]void IPriorityQueueOp<KeyValuePair<TKey,int>>.Enqueue(KeyValuePair<TKey,int>pair)=>Enqueue(pair.Key,pair.Value);[MethodImpl(AggressiveInlining)]public void Enqueue(TKey key,int value){var ix=indexes[value];if(ix<0){ix=indexes[value]=Count++;values[ix]=value;}keys[ix]=key;UpdateUp(ix);}[MethodImpl(AggressiveInlining)]public bool TryDequeue(out TKey key,out int value){if(Count==0){key=default(TKey);value=default(int);return false;}(key,value)=Dequeue();return true;}[MethodImpl(AggressiveInlining)]public bool TryDequeue(out KeyValuePair<TKey,int>result){if(Count==0){result=default(KeyValuePair<TKey,int>);return false;}result=Dequeue();return true;}[MethodImpl(AggressiveInlining)]public KeyValuePair<TKey,int>Dequeue(){indexes[values[0]]=-1;var res=KeyValuePair.Create(keys[0],values[0]);keys[0]=keys[ --Count];values[0]=values[Count];indexes[values[0]]=0;UpdateDown(0);return res;}[MethodImpl(AggressiveInlining)]private void UpdateUp(int i){var tar=keys[i];var tarVal=values[i];while(i>0){var p=(i-1)>>1;if(_comparer.Compare(tar,keys[p])>=0)break;keys[i]=keys[p];values[i]=values[p];indexes[values[i]]=i;i=p;}keys[i]=tar;values[i]=tarVal;indexes[values[i]]=i;}[MethodImpl(AggressiveInlining)]private void UpdateDown(int i){var tar=keys[i];var tarVal=values[i];var n=Count;var child=2*i+1;while(child<n){if(child!=n-1&&_comparer.Compare(keys[child],keys[child+1])>0)child++;if(_comparer.Compare(tar,keys[child])<=0)break;keys[i]=keys[child];values[i]=values[child];indexes[values[i]]=i;i=child;child=2*i+1;}keys[i]=tar;values[i]=tarVal;indexes[values[i]]=i;}public void Clear()=>Count=0;public ReadOnlySpan<TKey>UnorderdKeys()=>keys.AsSpan(0,Count);public ReadOnlySpan<int>UnorderdValues()=>values.AsSpan(0,Count);private class DebugView{private readonly PriorityQueueDijkstra<TKey,TKOp>pq;public DebugView(PriorityQueueDijkstra<TKey,TKOp>pq){this.pq=pq;}public KeyValuePair<TKey,int>[]Items{get{var count=pq.Count;var keys=pq.keys.AsSpan(0,count).ToArray();var values=pq.values.AsSpan(0,count).ToArray();Array.Sort(keys,values,pq._comparer);var arr=new KeyValuePair<TKey,int>[count];for(int i=0;i<arr.Length;i++)arr[i]=KeyValuePair.Create(keys[i],values[i]);return arr;}}}}}
namespace Kzrnm.Competitive{using static MethodImplOptions;public static class __ArrayExtension{[MethodImpl(AggressiveInlining)]public static T[]Fill<T>(this T[]arr,T value){arr.AsSpan().Fill(value);return arr;}[MethodImpl(AggressiveInlining)]public static T[]Sort<T>(this T[]arr){Array.Sort(arr);return arr;}[MethodImpl(AggressiveInlining)]public static string[]Sort(this string[]arr)=>Sort(arr,StringComparer.Ordinal);[MethodImpl(AggressiveInlining)]public static T[]Sort<T,U>(this T[]arr,Func<T,U>selector)where U:IComparable<U>{Array.Sort(arr.Select(selector).ToArray(),arr);return arr;}[MethodImpl(AggressiveInlining)]public static T[]Sort<T>(this T[]arr,Comparison<T>comparison){Array.Sort(arr,comparison);return arr;}[MethodImpl(AggressiveInlining)]public static T[]Sort<T>(this T[]arr,IComparer<T>comparer){Array.Sort(arr,comparer);return arr;}[MethodImpl(AggressiveInlining)]public static T[]Reverse<T>(this T[]arr){Array.Reverse(arr);return arr;}[MethodImpl(AggressiveInlining)]public static ref T Get<T>(this T[]arr,int index){if(index<0)index+=arr.Length;return ref arr[index];}[MethodImpl(AggressiveInlining)]public static ref readonly T GetOrDummy<T>(this ReadOnlySpan<T>arr,int index,T dummy=default){if((uint)index<(uint)arr.Length)return ref arr[index];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[MethodImpl(AggressiveInlining)]public static ref T GetOrDummy<T>(this Span<T>arr,int index,T dummy=default){if((uint)index<(uint)arr.Length)return ref arr[index];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[MethodImpl(AggressiveInlining)]public static ref T GetOrDummy<T>(this T[]arr,int index,T dummy=default){if((uint)index<(uint)arr.Length)return ref arr[index];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[MethodImpl(AggressiveInlining)]public static ref T GetOrDummy<T>(this T[][]arr,int index1,int index2,T dummy=default){if((uint)index1<(uint)arr.Length&&(uint)index2<(uint)arr[index1].Length)return ref arr[index1][index2];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}[MethodImpl(AggressiveInlining)]public static ref T GetOrDummy<T>(this T[][][]arr,int index1,int index2,int index3,T dummy=default){if((uint)index1<(uint)arr.Length&&(uint)index2<(uint)arr[index1].Length&&(uint)index3<(uint)arr[index1][index2].Length)return ref arr[index1][index2][index3];Dummy<T>.dummy=dummy;return ref Dummy<T>.dummy;}private static class Dummy<T>{public static T dummy;}}}
namespace System{public static class __CollectionExtension{public static TValue Get<TKey,TValue>(this IDictionary<TKey,TValue>dic,TKey key){dic.TryGetValue(key,out var v);return v;}public static(T Value,int Count)[]CompressCount<T>(this IEnumerable<T>collection){var e=collection.GetEnumerator();var list=new SimpleList<(T Value,int Count)>();if(!e.MoveNext())return Array.Empty<(T,int)>();var cur=e.Current;list.Add((cur,1));while(e.MoveNext()){if(EqualityComparer<T>.Default.Equals(cur,e.Current))list[^1].Count++;else{cur=e.Current;list.Add((cur,1));}}return list.ToArray();}}}
namespace Kzrnm.Competitive{using static MethodImplOptions;public static class __UpdateExtension{[MethodImpl(AggressiveInlining)]public static bool UpdateMax<T>(this ref T r,T val)where T:struct,IComparable<T>{if(r.CompareTo(val)<0){r=val;return true;}return false;}[MethodImpl(AggressiveInlining)]public static bool UpdateMin<T>(this ref T r,T val)where T:struct,IComparable<T>{if(r.CompareTo(val)>0){r=val;return true;}return false;}}}
namespace Kzrnm.Competitive{public static class Global{public static T[]NewArray<T>(int len0,T value)where T:struct=>new T[len0].Fill(value);public static T[]NewArray<T>(int len0,Func<T>factory){var arr=new T[len0];for(int i=0;i<arr.Length;i++)arr[i]=factory();return arr;}public static T[][]NewArray<T>(int len0,int len1,T value)where T:struct{var arr=new T[len0][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,value);return arr;}public static T[][]NewArray<T>(int len0,int len1,Func<T>factory){var arr=new T[len0][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,factory);return arr;}public static T[][][]NewArray<T>(int len0,int len1,int len2,T value)where T:struct{var arr=new T[len0][][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,len2,value);return arr;}public static T[][][]NewArray<T>(int len0,int len1,int len2,Func<T>factory){var arr=new T[len0][][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,len2,factory);return arr;}public static T[][][][]NewArray<T>(int len0,int len1,int len2,int len3,T value)where T:struct{var arr=new T[len0][][][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,len2,len3,value);return arr;}public static T[][][][]NewArray<T>(int len0,int len1,int len2,int len3,Func<T>factory){var arr=new T[len0][][][];for(int i=0;i<arr.Length;i++)arr[i]=NewArray(len1,len2,len3,factory);return arr;}}}
namespace Kzrnm.Competitive{public class EdgeContainer<TEdge>where TEdge:IGraphEdge{public int Length{get;}public bool IsDirected{get;}public readonly SimpleList<(int from,TEdge edge)>edges;public readonly int[]sizes;public readonly int[]rootSizes;public EdgeContainer(int size,bool isDirected){Length=size;IsDirected=isDirected;sizes=new int[size];rootSizes=isDirected?new int[size]:sizes;edges=new SimpleList<(int from,TEdge edge)>(size);}public void Add(int from,TEdge edge){ ++sizes[from];++rootSizes[edge.To];edges.Add((from,edge));}public CSR<TEdge>ToCSR()=>new CSR<TEdge>(Length,edges);}}
namespace Kzrnm.Competitive{public interface IGraph<TNode,TEdge>where TNode:IGraphNode<TEdge>where TEdge:IGraphEdge{CSR<TEdge>Edges{get;}TNode[]AsArray();TNode this[int index]{get;}int Length{get;}}public interface ITreeGraph<TNode,TEdge>where TNode:ITreeNode<TEdge>where TEdge:IGraphEdge{int Root{get;}TNode[]AsArray();TNode this[int index]{get;}int Length{get;}}public class SimpleGraph<TNode,TEdge>:IGraph<TNode,TEdge>where TNode:IGraphNode<TEdge>where TEdge:IGraphEdge{public CSR<TEdge>Edges{get;}internal TNode[]Nodes{get;}public TNode[]AsArray()=>Nodes;public TNode this[int index]=>Nodes[index];public int Length=>Nodes.Length;public SimpleGraph(TNode[]array,CSR<TEdge>edges){this.Nodes=array;this.Edges=edges;}}public class TreeGraph<TNode,TEdge>:ITreeGraph<TNode,TEdge>where TNode:ITreeNode<TEdge>where TEdge:IGraphEdge{internal TNode[]Nodes{get;}public TNode[]AsArray()=>Nodes;public TNode this[int index]=>Nodes[index];public int Length=>Nodes.Length;public int Root{get;}public TreeGraph(TNode[]array,int root){this.Root=root;this.Nodes=array;}}}
namespace Kzrnm.Competitive{public interface IReversable<T>where T:IGraphEdge{T Reversed(int from);}public interface IGraphEdge{int To{get;}}public interface IWGraphEdge<T>:IGraphEdge{T Value{get;}}public interface IGraphNode<out TEdge>where TEdge:IGraphEdge{int Index{get;}TEdge[]Roots{get;}TEdge[]Children{get;}bool IsDirected{get;}}public interface ITreeNode<TEdge>where TEdge:IGraphEdge{int Index{get;}TEdge Root{get;}TEdge[]Children{get;}int Depth{get;}}}
namespace Kzrnm.Competitive{public static class 最短経路BFS{public static uint[]ShortestPathBFS<TNode,TEdge>(this IGraph<TNode,TEdge>graph,int from)where TNode:IGraphNode<TEdge>where TEdge:IGraphEdge{var graphArr=graph.AsArray();var res=Global.NewArray(graphArr.Length,uint.MaxValue);var queue=new Queue<int>();queue.Enqueue(from);res[from]=0;while(queue.TryDequeue(out var cur)){foreach(var e in graphArr[cur].Children){var child=e.To;if(res[child].UpdateMin(res[cur]+1))queue.Enqueue(child);}}return res;}public static uint[]ShortestPathBFSReverse<TNode,TEdge>(this IGraph<TNode,TEdge>graph,int from)where TNode:IGraphNode<TEdge>where TEdge:IGraphEdge{var graphArr=graph.AsArray();var res=Global.NewArray(graphArr.Length,uint.MaxValue);var queue=new Queue<int>();queue.Enqueue(from);res[from]=0;while(queue.Count>0){var cur=queue.Dequeue();foreach(var e in graphArr[cur].Roots){var child=e.To;if(res[child].UpdateMin(res[cur]+1))queue.Enqueue(child);}}return res;}}}
namespace Kzrnm.Competitive{public interface IWGraph<T,TOp,TNode,TEdge>:IGraph<TNode,TEdge>where TOp:struct,IAdditionOperator<T>where TNode:IGraphNode<TEdge>where TEdge:IWGraphEdge<T>{}public interface IWTreeGraph<T,TOp,TNode,TEdge>:ITreeGraph<TNode,TEdge>where TOp:struct,IAdditionOperator<T>where TNode:ITreeNode<TEdge>where TEdge:IWGraphEdge<T>{}public class WGraph<T,TOp,TNode,TEdge>:IWGraph<T,TOp,TNode,TEdge>where TOp:struct,IAdditionOperator<T>where TNode:IGraphNode<TEdge>where TEdge:IWGraphEdge<T>{public CSR<TEdge>Edges{get;}internal TNode[]Nodes{get;}public TNode[]AsArray()=>Nodes;public TNode this[int index]=>Nodes[index];public int Length=>Nodes.Length;public WGraph(TNode[]array,CSR<TEdge>edges){this.Nodes=array;this.Edges=edges;}}public class WTreeGraph<T,TOp,TNode,TEdge>:IWTreeGraph<T,TOp,TNode,TEdge>where TOp:struct,IAdditionOperator<T>where TNode:ITreeNode<TEdge>where TEdge:IWGraphEdge<T>{internal TNode[]Nodes{get;}public TNode[]AsArray()=>Nodes;public TNode this[int index]=>Nodes[index];public int Length=>Nodes.Length;public int Root{get;}public WTreeGraph(TNode[]array,int root){this.Root=root;this.Nodes=array;}}}
namespace Kzrnm.Competitive{public class WGraphBuilder<T,S,TOp>where TOp:struct,IAdditionOperator<T>{protected static readonly TOp op=default;internal readonly EdgeContainer<WEdge<T,S>>edgeContainer;public WGraphBuilder(int size,bool isDirected){edgeContainer=new EdgeContainer<WEdge<T,S>>(size,isDirected);}public void Add(int from,int to,T value,S data)=>edgeContainer.Add(from,new WEdge<T,S>(to,value,data));public WGraph<T,TOp,WGraphNode<T,WEdge<T,S>>,WEdge<T,S>>ToGraph(){var res=new WGraphNode<T,WEdge<T,S>>[edgeContainer.Length];var csr=edgeContainer.ToCSR();var counter=new int[res.Length];var rootCounter=edgeContainer.IsDirected?new int[res.Length]:counter;var children=new WEdge<T,S>[res.Length][];var roots=edgeContainer.IsDirected?new WEdge<T,S>[res.Length][]:children;for(int i=0;i<res.Length;i++){if(children[i]==null)children[i]=new WEdge<T,S>[edgeContainer.sizes[i]];if(roots[i]==null)roots[i]=new WEdge<T,S>[edgeContainer.rootSizes[i]];res[i]=new WGraphNode<T,WEdge<T,S>>(i,roots[i],children[i]);foreach(ref var e in csr.EList.AsSpan(csr.Start[i],csr.Start[i+1]-csr.Start[i])){if(roots[e.To]==null)roots[e.To]=new WEdge<T,S>[edgeContainer.rootSizes[e.To]];children[i][counter[i]++]=e;roots[e.To][rootCounter[e.To]++]=e.Reversed(i);}}return new WGraph<T,TOp,WGraphNode<T,WEdge<T,S>>,WEdge<T,S>>(res,csr);}public WTreeGraph<T,TOp,WTreeNode<T,WEdge<T,S>>,WEdge<T,S>>ToTree(int root=0){var res=new WTreeNode<T,WEdge<T,S>>[edgeContainer.Length];var children=new SimpleList<WEdge<T,S>>[res.Length];foreach(var(from,e)in edgeContainer.edges){if(children[from]==null)children[from]=new SimpleList<WEdge<T,S>>();if(children[e.To]==null)children[e.To]=new SimpleList<WEdge<T,S>>();children[from].Add(e);children[e.To].Add(e.Reversed(from));}if(edgeContainer.Length==1){return new WTreeGraph<T,TOp,WTreeNode<T,WEdge<T,S>>,WEdge<T,S>>(new WTreeNode<T,WEdge<T,S>>[1]{new WTreeNode<T,WEdge<T,S>>(root,WEdge<T,S>.None,0,default,Array.Empty<WEdge<T,S>>())},root);}res[root]=new WTreeNode<T,WEdge<T,S>>(root,WEdge<T,S>.None,0,default,children[root]?.ToArray()??Array.Empty<WEdge<T,S>>());var queue=new Queue<(int parent,int child,T value,S data)>();foreach(var e in res[root].Children){queue.Enqueue((root,e.To,e.Value,e.Data));}while(queue.Count>0){var(parent,cur,value,data)=queue.Dequeue();IList<WEdge<T,S>>childrenBuilder;if(parent==-1)childrenBuilder=children[cur];else{childrenBuilder=new SimpleList<WEdge<T,S>>(children[cur].Count);foreach(var e in children[cur])if(e.To!=parent)childrenBuilder.Add(e);}var childrenArr=childrenBuilder.ToArray();res[cur]=new WTreeNode<T,WEdge<T,S>>(cur,new WEdge<T,S>(parent,value,data),res[parent].Depth+1,op.Add(res[parent].DepthLength,value),childrenArr);foreach(var e in childrenArr){queue.Enqueue((cur,e.To,e.Value,e.Data));}}return new WTreeGraph<T,TOp,WTreeNode<T,WEdge<T,S>>,WEdge<T,S>>(res,root);}}public readonly struct WEdge<T,S>:IWGraphEdge<T>,IReversable<WEdge<T,S>>,IEquatable<WEdge<T,S>>{public static WEdge<T,S>None{get;}=new WEdge<T,S>(-1,default,default);public WEdge(int to,T value,S data){To=to;Value=value;Data=data;}public int To{get;}public T Value{get;}public S Data{get;}public override bool Equals(object obj)=>obj is WEdge<T,S>edge&&this.Equals(edge);public bool Equals(WEdge<T,S>other)=>this.To==other.To&&EqualityComparer<T>.Default.Equals(this.Value,other.Value)&&EqualityComparer<S>.Default.Equals(this.Data,other.Data);public override int GetHashCode()=>HashCode.Combine(this.To,this.Value);public static bool operator==(WEdge<T,S>left,WEdge<T,S>right)=>left.Equals(right);public static bool operator!=(WEdge<T,S>left,WEdge<T,S>right)=>!(left==right);public override string ToString()=>$"to:{To}, Value:{Value}, Data:{Data}";public WEdge<T,S>Reversed(int from)=>new WEdge<T,S>(from,Value,Data);}}
namespace Kzrnm.Competitive{public class WGraphNode<T,TEdge>:IGraphNode<TEdge>,IEquatable<WGraphNode<T,TEdge>>where TEdge:IWGraphEdge<T>{public WGraphNode(int i,TEdge[]roots,TEdge[]children){this.Index=i;this.Roots=roots;this.Children=children;}public int Index{get;}public TEdge[]Roots{get;}public TEdge[]Children{get;}public bool IsDirected=>Roots!=Children;public override string ToString()=>$"children: {string.Join(",",Children)}";public override bool Equals(object obj)=>obj is WGraphNode<T,TEdge>d&&this.Equals(d);public bool Equals(WGraphNode<T,TEdge>other)=>this.Index==other.Index;public override int GetHashCode()=>this.Index;}public class WTreeNode<T,TEdge>:ITreeNode<TEdge>,IEquatable<WTreeNode<T,TEdge>>where TEdge:IWGraphEdge<T>{public WTreeNode(int i,TEdge root,int depth,T depthLength,TEdge[]children){this.Index=i;this.Root=root;this.Children=children;this.Depth=depth;this.DepthLength=depthLength;}public int Index{get;}public TEdge Root{get;}public TEdge[]Children{get;}public int Depth{get;}public T DepthLength{get;}public override string ToString()=>$"children: {string.Join(",",Children)}";public override bool Equals(object obj)=>obj is WTreeNode<T,TEdge>node&&this.Equals(node);public bool Equals(WTreeNode<T,TEdge>other)=>other!=null&&this.Index==other.Index;public override int GetHashCode()=>this.Index;}}
internal partial class Program{static void Main()=>new Program(new PropertyConsoleReader(),new ConsoleWriter()).Run();public PropertyConsoleReader cr;public ConsoleWriter cw;public Program(PropertyConsoleReader r,ConsoleWriter w){this.cr=r;this.cw=w;CultureInfo.CurrentCulture=CultureInfo.InvariantCulture;}public void Run(){var sw=cw.StreamWriter;int Q=__ManyTestCases?cr.Int:1;for(;Q>0;Q--){var res=Calc();if(res is double d)sw.WriteLine(d.ToString("0.####################",CultureInfo.InvariantCulture));else if(res is bool b)sw.WriteLine(YesNo(b));else if(res is char[]chrs)sw.WriteLine(chrs);else if(res!=null&&res!=cw)sw.WriteLine(res.ToString());}cw.Flush();}}
#endregion Expanded by https://github.com/naminodarie/SourceExpander

提出情報

ジャッジ結果