#1196609 (C#) No.1 道のショートカット

• 問題: No.1 道のショートカット
• ユーザー: aketijyuuzou
• 提出日時: 2026-11-02 22:38:41
• 言語: C# (.NET 10.0.403 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 15,195 bytes
• コンパイル時間: 13,019 ms
• コンパイル使用メモリ: 171,904 KB
• 実行使用メモリ: 35,584 KB
• 最終ジャッジ日時: 2026-11-02 22:39:01
• 合計ジャッジ時間: 17,825 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 1 WA * 3
other	AC * 3 WA * 36

コンパイルメッセージ

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

ソースコード

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

// https://yukicoder.me/problems/no/1
class Program
{
    static string InputPattern = "InputX";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("3");
            WillReturn.Add("100");
            WillReturn.Add("3");
            WillReturn.Add("1 2 1");
            WillReturn.Add("2 3 3");
            WillReturn.Add("10 90 10");
            WillReturn.Add("10 10 50");
            //20
            //1→3 と行くと コスト10だが、単位時間が50掛かる。
            //1→2→3 と行くと 一文無しになるが、20単位時間なので早いのでこちらを選択する。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("100");
            WillReturn.Add("3");
            WillReturn.Add("1 2 1");
            WillReturn.Add("2 3 3");
            WillReturn.Add("1 100 10");
            WillReturn.Add("10 10 50");
            //50
            //1→2→3 と行くと時間は20と短いが、コスト101かかるため選択できない。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10");
            WillReturn.Add("10");
            WillReturn.Add("19");
            WillReturn.Add("1 1 2 4 5 1 3 4 6 4 6 4 5 7 8 2 3 4 9");
            WillReturn.Add("3 5 5 5 6 7 7 7 7 8 8 9 9 9 9 10 10 10 10");
            WillReturn.Add("8 6 8 7 6 6 9 9 7 6 9 7 7 8 7 6 6 8 6");
            WillReturn.Add("8 9 10 4 10 3 5 9 3 4 1 8 3 1 3 6 6 10 4");
            //-1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct EdgeInfoDef
    {
        internal long ToNode;
        internal long Cost;
        internal long Time;
    }
    static Dictionary<long, List<EdgeInfoDef>> mEdgeInfoListDict = new Dictionary<long, List<EdgeInfoDef>>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        long N = long.Parse(InputList[0]);
        long C = long.Parse(InputList[1]);
        long[] SArr = InputList[3].Split(' ').Select(X => long.Parse(X)).ToArray();
        long[] TArr = InputList[4].Split(' ').Select(X => long.Parse(X)).ToArray();
        long[] YArr = InputList[5].Split(' ').Select(X => long.Parse(X)).ToArray();
        long[] MArr = InputList[6].Split(' ').Select(X => long.Parse(X)).ToArray();

        for (long I = 0; I <= SArr.GetUpperBound(0); I++) {
            long FromNode = SArr[I];
            EdgeInfoDef WillAdd;
            WillAdd.ToNode = TArr[I];
            WillAdd.Cost = YArr[I];
            WillAdd.Time = MArr[I];

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

        // 時間合計[残金]な1点更新区間Min取得なセグ木を、ノードごとに持つ
        var SegTreeDict = new Dictionary<long, SegmentTree>();
        for (long I = 1; I <= N; I++) {
            SegTreeDict[I] = new SegmentTree(C, long.MaxValue);
        }

        // 最良優先探索
        var InsPQueue_Arr = new PQueue_Arr();
        PQueue_Arr.PQueueJyoutaiDef WillEnqueue;
        WillEnqueue.CurrNode = 1;
        WillEnqueue.TimeSum = 0;
        WillEnqueue.RestMoney = C;
        InsPQueue_Arr.Enqueue(WillEnqueue);

        bool HasAnswer = false;
        long Answer = long.MaxValue;

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

            // クリア判定
            if (Dequeued.CurrNode == N) {
                HasAnswer = true;
                Answer = Math.Min(Answer, Dequeued.TimeSum);
                continue;
            }
            
            // 枝切り
            if (Dequeued.TimeSum <= Answer) continue;

            if (mEdgeInfoListDict.ContainsKey(Dequeued.CurrNode)) {
                foreach (EdgeInfoDef EachEdgeInfo in mEdgeInfoListDict[Dequeued.CurrNode]) {
                    WillEnqueue.CurrNode = EachEdgeInfo.ToNode;
                    WillEnqueue.TimeSum = Dequeued.TimeSum + EachEdgeInfo.Time;
                    WillEnqueue.RestMoney = Dequeued.RestMoney - EachEdgeInfo.Cost;

                    if (WillEnqueue.RestMoney < 0) continue;

                    // 枝切り
                    long RangeSta = WillEnqueue.RestMoney;
                    long RangeEnd = SegTreeDict[WillEnqueue.CurrNode].GetUB();
                    long RangeMin = SegTreeDict[WillEnqueue.CurrNode].Internal_Query(RangeSta, RangeEnd);
                    if (RangeMin <= WillEnqueue.TimeSum) {
                        continue;
                    }
                    SegTreeDict[WillEnqueue.CurrNode][WillEnqueue.RestMoney] = WillEnqueue.TimeSum;
                    InsPQueue_Arr.Enqueue(WillEnqueue);
                }
            }
        }

        if (HasAnswer) {
            Console.WriteLine(Answer);
        }
        else {
            Console.WriteLine(-1);
        }
    }
}

#region PQueue_Arr
// 優先度付きキュー
internal class PQueue_Arr
{
    internal struct PQueueJyoutaiDef : IComparable<PQueueJyoutaiDef>
    {
        internal long CurrNode;
        internal long TimeSum;
        internal long RestMoney;

        // OrderBy 時間合計 ASC , 残金 DESC
        public int CompareTo(PQueueJyoutaiDef pOtherIns)
        {
            if (TimeSum != pOtherIns.TimeSum) {
                return TimeSum.CompareTo(pOtherIns.TimeSum);
            }
            return pOtherIns.RestMoney.CompareTo(RestMoney);
        }
    }

    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 PQueueJyoutaiDef Peek()
    {
        return mHeapArr[1];
    }

    // エンキュー処理
    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].CompareTo(mHeapArr[CurrNode]) > 0) {
            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(int pRootNode)
    {
        if (mHeapArrCnt <= 1) {
            return;
        }

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

        // 左の子、自分、右の子で値が最小のノードを選ぶ
        int SmallestNode = pRootNode;

        if (Left <= mHeapArrCnt && mHeapArr[Left].CompareTo(mHeapArr[SmallestNode]) < 0) {
            SmallestNode = Left;
        }
        if (Right <= mHeapArrCnt && mHeapArr[Right].CompareTo(mHeapArr[SmallestNode]) < 0) {
            SmallestNode = Right;
        }

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

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

#region SegmentTree
// SegmentTreeクラス (RMinQ and 1点更新)
internal class SegmentTree
{
    private long[] mTreeNodeArr;
    private long UB; // 木のノードの配列のUB
    private long mLeafCnt; // 葉ノードの数
    private long mExternalArrUB;

    // ノードの添字を引数とし、範囲の開始添字と終了添字を持つ配列
    private struct RangeInfoDef
    {
        internal long StaInd;
        internal long EndInd;
    }
    private RangeInfoDef[] mRangeInfo;

    // ノードのIndexの列挙を返す
    internal IEnumerable<long> GetNodeIndEnum()
    {
        for (long I = 0; I <= mExternalArrUB; I++) {
            yield return I;
        }
    }

    // 木のノードのUBを返す
    internal long GetUB()
    {
        return mExternalArrUB;
    }

    // コンストラクタその1
    // 引数1 外部IndのUB
    // 引数2 単位元
    internal SegmentTree(long pExternalArrUB, long pInitVal)
    {
        mExternalArrUB = pExternalArrUB;

        ConstructorTreeInit();

        // すべての値をpInitValに
        for (long I = 0; I <= UB; I++) {
            mTreeNodeArr[I] = pInitVal;
        }
    }

    // コンストラクタその2
    // 引数1 初期化用の配列
    // 引数2 単位元
    internal SegmentTree(long[] pInitArr, long pInitVal)
    {
        mExternalArrUB = pInitArr.GetUpperBound(0);

        ConstructorTreeInit();

        // すべての値をpInitValに
        for (long I = 0; I <= UB; I++) {
            mTreeNodeArr[I] = pInitVal;
        }

        for (long I = 0; I <= pInitArr.GetUpperBound(0); I++) {
            long TreeNode = DeriveTreeNode(I);
            mTreeNodeArr[TreeNode] = pInitArr[I];
        }

        // 木DPの要領で、葉から根に伝播
        ExecTreeDP();
    }

    // コンストラクタその3
    // 引数1 初期化用のList
    // 引数2 単位元
    internal SegmentTree(List<long> pInitList, long pInitVal)
    {
        mExternalArrUB = pInitList.Count - 1;

        ConstructorTreeInit();

        // すべての値をpInitValに
        for (long I = 0; I <= UB; I++) {
            mTreeNodeArr[I] = pInitVal;
        }

        for (long I = 0; I <= pInitList.Count - 1; I++) {
            long TreeNode = DeriveTreeNode(I);
            mTreeNodeArr[TreeNode] = pInitList[(int)I];
        }

        // 木DPの要領で、葉から根に伝播
        ExecTreeDP();
    }

    // コンストラクタのヘルパメソッド(木の初期化)
    private void ConstructorTreeInit()
    {
        // 簡単のため、葉ノード数を2のべき乗に
        long ArrLength = 0;
        for (long I = 1; I < long.MaxValue; I *= 2) {
            ArrLength += I;
            mLeafCnt = I;

            if (mExternalArrUB + 1 < mLeafCnt) break;
        }

        UB = ArrLength - 1;
        mTreeNodeArr = new long[UB + 1];

        // ノードの添字を引数とし、範囲の開始添字と終了添字を持つ配列の作成
        mRangeInfo = new RangeInfoDef[UB + 1];
        for (long I = 0; I <= UB; I++) {
            if (I == 0) {
                RangeInfoDef WillSet1;
                WillSet1.StaInd = 0;
                WillSet1.EndInd = mLeafCnt - 1;
                mRangeInfo[I] = WillSet1;
                continue;
            }
            long ParentNode = DeriveParentNode(I);
            RangeInfoDef ParentRangeInfo = mRangeInfo[ParentNode];

            RangeInfoDef WillSet2;
            long Mid = (ParentRangeInfo.StaInd + ParentRangeInfo.EndInd) / 2;

            if (I % 2 == 1) { // 奇数ノードの場合
                WillSet2.StaInd = ParentRangeInfo.StaInd;
                WillSet2.EndInd = Mid;
            }
            else { // 偶数ノードの場合
                WillSet2.StaInd = Mid + 1;
                WillSet2.EndInd = ParentRangeInfo.EndInd;
            }
            mRangeInfo[I] = WillSet2;
        }
    }

    // 木DPの要領で、葉から根に伝播
    private void ExecTreeDP()
    {
        for (long I = UB; 0 < I; I--) {
            long SendNode = DeriveParentNode(I);
            mTreeNodeArr[SendNode] = Math.Min(mTreeNodeArr[SendNode], mTreeNodeArr[I]);
        }
    }

    // インデクサ
    internal long this[long pInd]
    {
        get
        {
            long CurrNode = DeriveTreeNode(pInd);
            return mTreeNodeArr[CurrNode];
        }
        set { Update(pInd, value); }
    }

    // 親ノードの添字を取得
    private long DeriveParentNode(long pTarget)
    {
        return (pTarget - 1) / 2;
    }

    // 子ノードの添字(小さいほう)を取得
    private long DeriveChildNode(long pTarget)
    {
        return pTarget * 2 + 1;
    }

    // 葉ノードの配列の添字を木の添字に変換して返す
    private long DeriveTreeNode(long pLeafArrInd)
    {
        long BaseInd = UB - mLeafCnt + 1;
        return BaseInd + pLeafArrInd;
    }

    // 葉ノードの配列のK番目の値をNewValに変更
    internal void Update(long pK, long pNewVal)
    {
        long CurrNode = DeriveTreeNode(pK);
        mTreeNodeArr[CurrNode] = pNewVal;

        // 登りながら更新
        while (CurrNode > 0) {
            CurrNode = DeriveParentNode(CurrNode);
            long ChildNode1 = DeriveChildNode(CurrNode);
            long ChildNode2 = ChildNode1 + 1;
            mTreeNodeArr[CurrNode] =
                Math.Min(mTreeNodeArr[ChildNode1], mTreeNodeArr[ChildNode2]);
        }
    }

    // 開始添字と終了添字とカレントノードを引数として、最小値を返す
    internal long Internal_Query(long pSearchStaInd, long pSearchEndInd)
    {
        return Private_Query(pSearchStaInd, pSearchEndInd, 0);
    }
    private long Private_Query(long pSearchStaInd, long pSearchEndInd, long pCurrNode)
    {
        long CurrNodeStaInd = mRangeInfo[pCurrNode].StaInd;
        long CurrNodeEndInd = mRangeInfo[pCurrNode].EndInd;

        // OverLapしてなければ、long.MaxValue
        if (CurrNodeEndInd < pSearchStaInd || pSearchEndInd < CurrNodeStaInd)
            return long.MaxValue;

        // 完全に含んでいれば、このノードの値
        if (pSearchStaInd <= CurrNodeStaInd && CurrNodeEndInd <= pSearchEndInd)
            return mTreeNodeArr[pCurrNode];

        // そうでなければ、2つの子の最小値
        long ChildNode1 = DeriveChildNode(pCurrNode);
        long ChildNode2 = ChildNode1 + 1;

        long ChildVal1 = Private_Query(pSearchStaInd, pSearchEndInd, ChildNode1);
        long ChildVal2 = Private_Query(pSearchStaInd, pSearchEndInd, ChildNode2);
        return Math.Min(ChildVal1, ChildVal2);
    }

    internal void DebugPrint()
    {
        for (long I = 0; I <= UB; I++) {
            Console.WriteLine("mTreeNodeArr[{0}] = {1}", I, mTreeNodeArr[I]);
        }
    }
}
#endregion