ABC164-E Two Currencies

問題へのリンク

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("3 2 1");
            WillReturn.Add("1 2 1 2");
            WillReturn.Add("1 3 2 4");
            WillReturn.Add("1 11");
            WillReturn.Add("1 2");
            WillReturn.Add("2 5");
            //2
            //14
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 4 1");
            WillReturn.Add("1 2 1 5");
            WillReturn.Add("1 3 4 4");
            WillReturn.Add("2 4 2 2");
            WillReturn.Add("3 4 1 1");
            WillReturn.Add("3 1");
            WillReturn.Add("3 1");
            WillReturn.Add("5 2");
            WillReturn.Add("6 4");
            //5
            //5
            //7
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("6 5 1");
            WillReturn.Add("1 2 1 1");
            WillReturn.Add("1 3 2 1");
            WillReturn.Add("2 4 5 1");
            WillReturn.Add("3 5 11 1");
            WillReturn.Add("1 6 50 1");
            WillReturn.Add("1 10000");
            WillReturn.Add("1 3000");
            WillReturn.Add("1 700");
            WillReturn.Add("1 100");
            WillReturn.Add("1 1");
            WillReturn.Add("100 1");
            //1
            //9003
            //14606
            //16510
            //16576
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("4 6 1000000000");
            WillReturn.Add("1 2 50 1");
            WillReturn.Add("1 3 50 5");
            WillReturn.Add("1 4 50 7");
            WillReturn.Add("2 3 50 2");
            WillReturn.Add("2 4 50 4");
            WillReturn.Add("3 4 50 3");
            WillReturn.Add("10 2");
            WillReturn.Add("4 4");
            WillReturn.Add("5 5");
            WillReturn.Add("7 7");
            //1
            //3
            //5
        }
        else if (InputPattern == "Input5") {
            WillReturn.Add("2 1 0");
            WillReturn.Add("1 2 1 1");
            WillReturn.Add("1 1000000000");
            WillReturn.Add("1 1");
            //1000000001
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long mN;
    static long mM;
    static long mS;

    struct EdgeInfoDef
    {
        internal long ToNode;
        internal long CostSilver;
        internal long CostMinute;
    }
    // 隣接リスト
    static Dictionary<long, List<EdgeInfoDef>> mEdgeListDict = new Dictionary<long, List<EdgeInfoDef>>();
    static long mCostSilverSum;

    // ノードごとの金貨を銀貨に交換する情報
    struct CDInfoDef
    {
        internal long C;
        internal long D;
    }
    static Dictionary<long, CDInfoDef> mCDInfoDict = new Dictionary<long, CDInfoDef>();

    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];
        mM = wkArr[1];
        mS = wkArr[2];

        foreach (string EachStr in InputList.Skip(1).Take((int)mM)) {
            SplitAct(EachStr);

            long FromNode = wkArr[0];
            long ToNode = wkArr[1];
            long CostSilver = wkArr[2];
            long CostMinute = wkArr[3];
            mCostSilverSum += CostSilver;

            if (mEdgeListDict.ContainsKey(FromNode) == false) {
                mEdgeListDict[FromNode] = new List<EdgeInfoDef>();
            }
            EdgeInfoDef WillAdd1;
            WillAdd1.ToNode = ToNode;
            WillAdd1.CostSilver = CostSilver;
            WillAdd1.CostMinute = CostMinute;
            mEdgeListDict[FromNode].Add(WillAdd1);

            if (mEdgeListDict.ContainsKey(ToNode) == false) {
                mEdgeListDict[ToNode] = new List<EdgeInfoDef>();
            }
            EdgeInfoDef WillAdd2;
            WillAdd2.ToNode = FromNode;
            WillAdd2.CostSilver = CostSilver;
            WillAdd2.CostMinute = CostMinute;
            mEdgeListDict[ToNode].Add(WillAdd2);
        }

        int NodeID = 1;
        for (int I = (int)mM + 1; I <= InputList.Count - 1; I++) {
            SplitAct(InputList[I]);

            CDInfoDef WillAdd;
            WillAdd.C = wkArr[0];
            WillAdd.D = wkArr[1];

            mCDInfoDict[NodeID] = WillAdd;
            NodeID++;
        }

        Solve();
    }

    // 最小の分数[ノード]なDict
    static Dictionary<long, long> mAnswerDict = new Dictionary<long, long>();

    // Dequeされた中で、最大の銀貨の枚数[ノード]なDict
    static Dictionary<long, long> mMaxSilverCoinCntDict = new Dictionary<long, long>();

    static void Solve()
    {
        var InsPQueue = new PQueue();

        PQueue.PQueueJyoutaiDef WillEnqueue;
        WillEnqueue.Node = 1;
        WillEnqueue.SilverCoinCnt = mS;
        WillEnqueue.MinuteSum = 0;
        InsPQueue.Enqueue(WillEnqueue);

        var NeedSet = new HashSet<long>();
        for (long I = 2; I <= mN; I++) {
            NeedSet.Add(I);
        }

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

            var EnqueueList = new List<PQueue.PQueueJyoutaiDef>();

            if (mAnswerDict.ContainsKey(Dequeued.Node) == false) {
                mAnswerDict[Dequeued.Node] = Dequeued.MinuteSum;
            }

            if (mMaxSilverCoinCntDict.ContainsKey(Dequeued.Node)) {
                if (mMaxSilverCoinCntDict[Dequeued.Node] >= Dequeued.SilverCoinCnt) {
                    continue;
                }
            }
            mMaxSilverCoinCntDict[Dequeued.Node] = Dequeued.SilverCoinCnt;

            NeedSet.Remove(Dequeued.Node);
            if (NeedSet.Count == 0) {
                break;
            }

            // 滞在して銀貨を増やす
            if (Dequeued.SilverCoinCnt < mCostSilverSum) {
                WillEnqueue.Node = Dequeued.Node;
                WillEnqueue.SilverCoinCnt = Dequeued.SilverCoinCnt + mCDInfoDict[Dequeued.Node].C;
                WillEnqueue.MinuteSum = Dequeued.MinuteSum + mCDInfoDict[Dequeued.Node].D;
                InsPQueue.Enqueue(WillEnqueue);
            }

            // 辺を経由して別ノードに移動
            if (mEdgeListDict.ContainsKey(Dequeued.Node) == false) {
                continue;
            }

            foreach (EdgeInfoDef EachEdgeInfo in mEdgeListDict[Dequeued.Node]) {
                // 銀貨不足なら移動は不可
                if (Dequeued.SilverCoinCnt < EachEdgeInfo.CostSilver) {
                    continue;
                }
                WillEnqueue.Node = EachEdgeInfo.ToNode;
                WillEnqueue.SilverCoinCnt = Dequeued.SilverCoinCnt - EachEdgeInfo.CostSilver;
                WillEnqueue.MinuteSum = Dequeued.MinuteSum + EachEdgeInfo.CostMinute;
                InsPQueue.Enqueue(WillEnqueue);
            }
        }

        foreach (var EachPair in mAnswerDict.OrderBy(pX => pX.Key)) {
            if (EachPair.Key >= 2) {
                Console.WriteLine(EachPair.Value);
            }
        }
    }
}

#region PQueue
// 優先度付きキュー
internal class PQueue
{
    internal struct PQueueJyoutaiDef
    {
        internal long Node;
        internal long SilverCoinCnt; // 持ってる銀貨の数
        internal long MinuteSum; // 分数の合計
    }

    private Dictionary<long, PQueueJyoutaiDef> mHeapDict = new Dictionary<long, PQueueJyoutaiDef>();

    internal bool IsEmpty()
    {
        return mHeapDict.Count == 0;
    }

    // エンキュー処理
    internal void Enqueue(PQueueJyoutaiDef pAddJyoutai)
    {
        long CurrNode = 1 + mHeapDict.Count;
        mHeapDict[CurrNode] = pAddJyoutai;

        while (1 < CurrNode && mHeapDict[CurrNode / 2].MinuteSum > mHeapDict[CurrNode].MinuteSum) {
            PQueueJyoutaiDef Swap = mHeapDict[CurrNode];
            mHeapDict[CurrNode] = mHeapDict[CurrNode / 2];
            mHeapDict[CurrNode / 2] = Swap;

            CurrNode /= 2;
        }
    }

    // デキュー処理
    internal PQueueJyoutaiDef Dequeue()
    {
        PQueueJyoutaiDef TopNode = mHeapDict[1];
        long LastNode = mHeapDict.Count;
        mHeapDict[1] = mHeapDict[LastNode];
        mHeapDict.Remove(LastNode);

        MinHeapify(1);
        return TopNode;
    }

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

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

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

        if (mHeapDict.ContainsKey(Left) && mHeapDict[Left].MinuteSum < Smallest) {
            Smallest = mHeapDict[Left].MinuteSum;
            SmallestNode = Left;
        }
        if (mHeapDict.ContainsKey(Right) && mHeapDict[Right].MinuteSum < Smallest) {
            Smallest = mHeapDict[Right].MinuteSum;
            SmallestNode = Right;
        }

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

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

解説

ダイクストラ法のアルゴリズムをアレンジして、
ノードと銀貨の枚数を状態に持ち、
プライオリティキューで、合計分数の少ない状態を優先してデキューしてます。