ABC342-E Last Train

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("6 7");
            WillReturn.Add("10 5 10 3 1 3");
            WillReturn.Add("13 5 10 2 3 4");
            WillReturn.Add("15 5 10 7 4 6");
            WillReturn.Add("3 10 2 4 2 5");
            WillReturn.Add("7 10 2 3 5 6");
            WillReturn.Add("5 3 18 2 2 3");
            WillReturn.Add("6 3 20 4 2 1");
            //55
            //56
            //58
            //60
            //17
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 5");
            WillReturn.Add("1000000000 1000000000 1000000000 1000000000 1 5");
            WillReturn.Add("5 9 2 6 2 3");
            WillReturn.Add("10 4 1 6 2 3");
            WillReturn.Add("1 1 1 1 3 5");
            WillReturn.Add("3 1 4 1 5 1");
            //1000000000000000000
            //Unreachable
            //1
            //Unreachable
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("16 20");
            WillReturn.Add("4018 9698 2850 3026 8 11");
            WillReturn.Add("2310 7571 7732 1862 13 14");
            WillReturn.Add("2440 2121 20 1849 11 16");
            WillReturn.Add("2560 5115 190 3655 5 16");
            WillReturn.Add("1936 6664 39 8822 4 16");
            WillReturn.Add("7597 8325 20 7576 12 5");
            WillReturn.Add("5396 1088 540 7765 15 1");
            WillReturn.Add("3226 88 6988 2504 13 5");
            WillReturn.Add("1838 7490 63 4098 8 3");
            WillReturn.Add("1456 5042 4 2815 14 7");
            WillReturn.Add("3762 6803 5054 6994 10 9");
            WillReturn.Add("9526 6001 61 8025 7 8");
            WillReturn.Add("5176 6747 107 3403 1 5");
            WillReturn.Add("2014 5533 2031 8127 8 11");
            WillReturn.Add("8102 5878 58 9548 9 10");
            WillReturn.Add("3788 174 3088 5950 3 13");
            WillReturn.Add("7778 5389 100 9003 10 15");
            WillReturn.Add("556 9425 9458 109 3 11");
            WillReturn.Add("5725 7937 10 3282 2 9");
            WillReturn.Add("6951 7211 8590 1994 15 12");
            //720358
            //77158
            //540926
            //255168
            //969295
            //Unreachable
            //369586
            //466218
            //343148
            //541289
            //42739
            //165772
            //618082
            //16582
            //591828
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mN;

    struct EdgeInfoDef
    {
        internal long StaTime;
        internal long Span;
        internal long Cnt;
        internal long Cost;
        internal long FromNode;
        internal long ToNode;
    }

    // 辺情報のList[終了ノード]なDict
    static Dictionary<long, List<EdgeInfoDef>> mEdgeInfoListDict =
        new Dictionary<long, List<EdgeInfoDef>>();

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        SplitAct(InputList[0]);
        mN = wkArr[0];

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            EdgeInfoDef WillAdd;
            WillAdd.StaTime = wkArr[0];
            WillAdd.Span = wkArr[1];
            WillAdd.Cnt = wkArr[2];
            WillAdd.Cost = wkArr[3];
            WillAdd.FromNode = wkArr[4];
            WillAdd.ToNode = wkArr[5];

            if (mEdgeInfoListDict.ContainsKey(WillAdd.ToNode) == false) {
                mEdgeInfoListDict[WillAdd.ToNode] = new List<EdgeInfoDef>();
            }
            mEdgeInfoListDict[WillAdd.ToNode].Add(WillAdd);
        }

        // ノードNに到着できる最大時間
        bool HasEdge = false;
        long MaxLastTime = long.MinValue;
        foreach (var EachPair in mEdgeInfoListDict) {
            if (EachPair.Key == mN) {
                foreach (EdgeInfoDef EachEdgeInfo in EachPair.Value) {
                    long LastTime = EachEdgeInfo.StaTime + EachEdgeInfo.Span * (EachEdgeInfo.Cnt - 1);
                    LastTime += EachEdgeInfo.Cost;
                    MaxLastTime = Math.Max(MaxLastTime, LastTime);
                    HasEdge = true;
                }
            }
        }

        // ノードNに到達不能の場合
        if (HasEdge == false) {
            for (long I = 1; I <= mN - 1; I++) {
                Console.WriteLine("Unreachable");
            }
            return;
        }

        Dictionary<long, long> ResultDict = Dijkstra(mN, MaxLastTime);
        var sb = new System.Text.StringBuilder();
        for (long I = 1; I <= mN - 1; I++) {
            if (ResultDict.ContainsKey(I)) {
                sb.Append(ResultDict[I]);
                sb.AppendLine();
            }
            else {
                sb.AppendLine("Unreachable");
            }
        }
        Console.Write(sb.ToString());
    }

    // ダイクストラ法で、各ノードの最遅到達時間を求める
    static Dictionary<long, long> Dijkstra(long pStaNode, long pMaxLastTime)
    {
        var InsPQueue = new PQueue_Arr();

        // 最遅到達時間[確定ノード]なDict
        var KakuteiNodeDict = new Dictionary<long, long>();
        KakuteiNodeDict.Add(pStaNode, pMaxLastTime);

        // Enqueue処理
        Action<long, long> EnqueueAct = (pToNode, pCurrTime) =>
        {
            if (mEdgeInfoListDict.ContainsKey(pToNode) == false) {
                return;
            }

            foreach (EdgeInfoDef EachEdge in mEdgeInfoListDict[pToNode]) {
                // 確定ノードならContinue
                if (KakuteiNodeDict.ContainsKey(EachEdge.FromNode)) continue;

                long MaxTime;
                if (GetMaxTime(out MaxTime, EachEdge, pCurrTime)) {
                    long NewMaxTimeCost = MaxTime;
                    PQueue_Arr.PQueueJyoutaiDef WillEnqueue;
                    WillEnqueue.Node = EachEdge.FromNode;
                    WillEnqueue.Val = NewMaxTimeCost;
                    InsPQueue.Enqueue(WillEnqueue);
                }
            }
        };
        EnqueueAct(pStaNode, pMaxLastTime);

        while (InsPQueue.IsEmpty() == false) {
            PQueue_Arr.PQueueJyoutaiDef Dequeued = InsPQueue.Dequeue();

            // 確定ノードならcontinue
            if (KakuteiNodeDict.ContainsKey(Dequeued.Node)) continue;

            KakuteiNodeDict.Add(Dequeued.Node, Dequeued.Val);
            EnqueueAct(Dequeued.Node, Dequeued.Val);
        }

        return KakuteiNodeDict;
    }

    // 現在時間と枝情報を引数とし、二分探索で最遅の乗車時間を求める
    static bool GetMaxTime(out long pMaxTime, EdgeInfoDef pEdgeInfo, long pCurrTime)
    {
        pMaxTime = -1;

        long L = 0;
        long R = pEdgeInfo.Cnt - 1;

        long MinVal = pEdgeInfo.StaTime + pEdgeInfo.Span * L + pEdgeInfo.Cost;
        long MaxVal = pEdgeInfo.StaTime + pEdgeInfo.Span * R + pEdgeInfo.Cost;

        // 特殊ケース1
        if (MaxVal <= pCurrTime) {
            pMaxTime = MaxVal - pEdgeInfo.Cost;
            return true;
        }

        // 特殊ケース2
        if (MinVal > pCurrTime) {
            return false;
        }

        while (L + 1 < R) {
            long Mid = (L + R) / 2;
            long CurrVal = pEdgeInfo.StaTime + pEdgeInfo.Span * Mid + pEdgeInfo.Cost;

            if (CurrVal <= pCurrTime) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }

        pMaxTime = pEdgeInfo.StaTime + pEdgeInfo.Span * L + pEdgeInfo.Cost;
        pMaxTime -= pEdgeInfo.Cost;
        return true;
    }
}

#region PQueue_Arr
// 優先度付きキュー (根のValが最大)
internal class PQueue_Arr
{
    internal struct PQueueJyoutaiDef
    {
        internal long Node;
        internal long Val;
    }

    private PQueueJyoutaiDef[] mHeapArr;
    private long mHeapArrCnt = 0;

    // コンストラクタ
    internal PQueue_Arr()
    {
        mHeapArr = new PQueueJyoutaiDef[65535];
    }

    internal bool IsEmpty()
    {
        return mHeapArrCnt == 0;
    }

    internal long Count()
    {
        return mHeapArrCnt;
    }

    internal long Peek()
    {
        return mHeapArr[1].Val;
    }

    // エンキュー処理
    internal void Enqueue(PQueueJyoutaiDef pAddJyoutai)
    {
        long CurrNode = 1 + mHeapArrCnt;
        if (mHeapArr.GetUpperBound(0) < CurrNode) {
            ExtendArr();
        }

        mHeapArr[CurrNode] = pAddJyoutai;
        mHeapArrCnt++;

        while (1 < CurrNode && mHeapArr[CurrNode / 2].Val < mHeapArr[CurrNode].Val) {
            PQueueJyoutaiDef Swap = mHeapArr[CurrNode];
            mHeapArr[CurrNode] = mHeapArr[CurrNode / 2];
            mHeapArr[CurrNode / 2] = Swap;

            CurrNode /= 2;
        }
    }

    // 配列のExtend
    private void ExtendArr()
    {
        PQueueJyoutaiDef[] NewHeapArr = new PQueueJyoutaiDef[mHeapArrCnt * 2];
        mHeapArr.CopyTo(NewHeapArr, 0);
        mHeapArr = NewHeapArr;
    }

    // デキュー処理
    internal PQueueJyoutaiDef Dequeue()
    {
        PQueueJyoutaiDef TopNode = mHeapArr[1];
        long LastNode = mHeapArrCnt;
        mHeapArr[1] = mHeapArr[LastNode];
        mHeapArrCnt--;

        MinHeapify(1);
        return TopNode;
    }

    // 根ノードを指定し、根から葉へヒープ構築
    private void MinHeapify(long pRootNode)
    {
        if (mHeapArrCnt <= 1) {
            return;
        }

        long Left = pRootNode * 2;
        long Right = pRootNode * 2 + 1;

        // 左の子、自分、右の子で値が最大のノードを選ぶ
        long Smallest = mHeapArr[pRootNode].Val;
        long SmallestNode = pRootNode;

        if (Left <= mHeapArrCnt && mHeapArr[Left].Val > Smallest) {
            Smallest = mHeapArr[Left].Val;
            SmallestNode = Left;
        }
        if (Right <= mHeapArrCnt && mHeapArr[Right].Val > Smallest) {
            Smallest = mHeapArr[Right].Val;
            SmallestNode = Right;
        }

        // 子ノードのほうが大きい場合
        if (SmallestNode != pRootNode) {
            PQueueJyoutaiDef Swap = mHeapArr[SmallestNode];
            mHeapArr[SmallestNode] = mHeapArr[pRootNode];
            mHeapArr[pRootNode] = Swap;

            // 再帰的に呼び出し
            MinHeapify(SmallestNode);
        }
    }
}
#endregion

解説

クリティカルパスの最遅開始時間を求める感覚で
逆辺でダイクストラ法を行ってます。