#1136157 (C#) No.3326 岩井星人の帰星

• 問題: No.3326 岩井星人の帰星
• ユーザー: aketijyuuzou
• 提出日時: 2025-11-23 20:22:03
• 言語: C# (.NET 8.0.404)
• 結果: WA
• 実行時間: -
• コード長: 7,868 bytes
• コンパイル時間: 8,430 ms
• コンパイル使用メモリ: 170,560 KB
• 実行使用メモリ: 190,236 KB
• 最終ジャッジ日時: 2025-11-23 20:22:43
• 合計ジャッジ時間: 36,192 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

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

コンパイルメッセージ

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

ソースコード

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

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

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

        if (InputPattern == "Input1") {
            WillReturn.Add("6 6");
            WillReturn.Add("1 2");
            WillReturn.Add("1 3");
            WillReturn.Add("2 6");
            WillReturn.Add("3 4");
            WillReturn.Add("4 5");
            WillReturn.Add("5 6");
            WillReturn.Add("1");
            WillReturn.Add("4 1 ");
            //Yes
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 2");
            WillReturn.Add("1 2");
            WillReturn.Add("1 3");
            WillReturn.Add("1");
            WillReturn.Add("3 1 ");
            //No
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("10 11");
            WillReturn.Add("1 2");
            WillReturn.Add("2 3");
            WillReturn.Add("3 4");
            WillReturn.Add("4 8");
            WillReturn.Add("4 5");
            WillReturn.Add("5 6");
            WillReturn.Add("6 7");
            WillReturn.Add("6 8");
            WillReturn.Add("7 8");
            WillReturn.Add("8 9");
            WillReturn.Add("9 10");
            WillReturn.Add("2");
            WillReturn.Add("7 0");
            WillReturn.Add("6 0");
            //Yes
            //6
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        pStr = pStr.TrimEnd();
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    // 隣接リスト
    static Dictionary<long, List<long>> mToNodeListDict = new Dictionary<long, List<long>>();

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

        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

        SplitAct(InputList[0]);
        long N = wkArr[0];
        long M = wkArr[1];

        foreach (string EachStr in InputList.Skip(1).Take((int)M)) {
            SplitAct(EachStr);
            long FromNode = wkArr[0];
            long ToNode = wkArr[1];

            if (mToNodeListDict.ContainsKey(FromNode) == false) {
                mToNodeListDict[FromNode] = new List<long>();
            }
            if (mToNodeListDict.ContainsKey(ToNode) == false) {
                mToNodeListDict[ToNode] = new List<long>();
            }
            mToNodeListDict[FromNode].Add(ToNode);
            mToNodeListDict[ToNode].Add(FromNode);
        }

        var Ins_PQueue_Arr = new PQueue_Arr();
        PQueue_Arr.PQueueJyoutaiDef WillEnqueue1;
        foreach (string EachStr in InputList.Skip(1 + (int)M + 1)) {
            SplitAct(EachStr);
            WillEnqueue1.CurrNode = wkArr[0];
            WillEnqueue1.RestMove = wkArr[1];
            Ins_PQueue_Arr.Enqueue(WillEnqueue1);
        }

        // 多始点BFS
        var BlockedSet = new HashSet<long>();
        while (Ins_PQueue_Arr.IsEmpty() == false) {
            PQueue_Arr.PQueueJyoutaiDef Dequeued1 = Ins_PQueue_Arr.Dequeue();
            BlockedSet.Add(Dequeued1.CurrNode);

            if (Dequeued1.RestMove == 0) continue;
            if (mToNodeListDict.ContainsKey(Dequeued1.CurrNode)) {
                foreach (long EachToNode in mToNodeListDict[Dequeued1.CurrNode]) {
                    if (BlockedSet.Contains(EachToNode) == false) {
                        WillEnqueue1.CurrNode = EachToNode;
                        WillEnqueue1.RestMove = Dequeued1.RestMove - 1;
                        Ins_PQueue_Arr.Enqueue(WillEnqueue1);
                    }
                }
            }
        }

        if (BlockedSet.Contains(1)) {
            Console.WriteLine("No");
            return;
        }

        var Que = new Queue<JyoutaiDefBFS>();
        JyoutaiDefBFS WillEnqueue2;
        WillEnqueue2.CurrNode = 1;
        WillEnqueue2.Level = 0;
        Que.Enqueue(WillEnqueue2);

        var VisitedSet = new HashSet<long>();
        while (Que.Count > 0) {
            JyoutaiDefBFS Dequeued2 = Que.Dequeue();

            if (Dequeued2.CurrNode == N) {
                Console.WriteLine("Yes");
                Console.WriteLine(Dequeued2.Level);
                return;
            }

            if (mToNodeListDict.ContainsKey(Dequeued2.CurrNode)) {
                foreach (long EachToNode in mToNodeListDict[Dequeued2.CurrNode]) {
                    if (VisitedSet.Add(EachToNode)) {
                        WillEnqueue2.CurrNode = EachToNode;
                        WillEnqueue2.Level = Dequeued2.Level + 1;
                        Que.Enqueue(WillEnqueue2);
                    }
                }
            }
        }
    }

    struct JyoutaiDefBFS
    {
        internal long CurrNode;
        internal long Level;
    }
}

#region PQueue_Arr
// 内部で配列使用の優先度付きキュー (根のRestMoveが最大)
internal class PQueue_Arr
{
    internal struct PQueueJyoutaiDef
    {
        internal long CurrNode;
        internal long RestMove;
    }

    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 void Enqueue(PQueueJyoutaiDef pAddJyoutai)
    {
        long CurrNode = 1 + mHeapArrCnt;
        if (mHeapArr.GetUpperBound(0) < CurrNode) {
            ExtendArr();
        }

        mHeapArr[CurrNode] = pAddJyoutai;
        mHeapArrCnt++;

        while (1 < CurrNode && mHeapArr[CurrNode / 2].RestMove < mHeapArr[CurrNode].RestMove) {
            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--;

        MaxHeapify(1);
        return TopNode;
    }

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

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

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

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

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

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