ABC481-D Autopilot

問題へのリンク

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("7 10 2 1");
            WillReturn.Add("2 5");
            WillReturn.Add("2 4");
            WillReturn.Add("4 2");
            WillReturn.Add("4 3");
            WillReturn.Add("3 1");
            WillReturn.Add("3 5");
            WillReturn.Add("3 6");
            WillReturn.Add("5 6");
            WillReturn.Add("6 1");
            WillReturn.Add("6 7");
            //1
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("7 10 2 7");
            WillReturn.Add("2 5");
            WillReturn.Add("2 4");
            WillReturn.Add("4 2");
            WillReturn.Add("4 3");
            WillReturn.Add("3 1");
            WillReturn.Add("3 5");
            WillReturn.Add("3 6");
            WillReturn.Add("5 6");
            WillReturn.Add("6 1");
            WillReturn.Add("6 7");
            //2
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("2 1 1 2");
            WillReturn.Add("2 1");
            //-1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        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 = GetSplitArr(InputList[0]);
        long StaNode = wkArr[2];
        long GoalNode = wkArr[3];

        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            long FromNode = wkArr[0];
            long ToNode = wkArr[1];

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

        foreach (var EachPair in mToNodeListDict) {
            mToNodeListDict[EachPair.Key].Sort();
        }

        var InsLinkedList = new LinkedList<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.CurrNode = StaNode;
        WillEnqueue.Cost = 0;
        InsLinkedList.AddLast(WillEnqueue);

        // 最短コスト[ノード]
        var EdakiriDict = new Dictionary<long, long>();

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

        while (InsLinkedList.Count > 0) {
            JyoutaiDef Dequeued = InsLinkedList.First.Value;
            InsLinkedList.RemoveFirst();

            if (Dequeued.CurrNode == GoalNode) {
                Answer = Math.Min(Answer, Dequeued.Cost);
                HasAnswer = true;
                continue;
            }
            long CurrNode = Dequeued.CurrNode;

            if (EdakiriDict.ContainsKey(CurrNode)) {
                if (EdakiriDict[CurrNode] <= Dequeued.Cost) {
                    continue;
                }
            }
            EdakiriDict[CurrNode] = Dequeued.Cost;

            if (mToNodeListDict.ContainsKey(CurrNode)) {
                for (int I = 0; I <= mToNodeListDict[CurrNode].Count - 1; I++) {
                    long ToNode = mToNodeListDict[CurrNode][I];
                    if (I == 0) {
                        WillEnqueue.CurrNode = ToNode;
                        WillEnqueue.Cost = Dequeued.Cost;
                        InsLinkedList.AddFirst(WillEnqueue);
                    }
                    else {
                        WillEnqueue.CurrNode = ToNode;
                        WillEnqueue.Cost = Dequeued.Cost + 1;
                        InsLinkedList.AddLast(WillEnqueue);
                    }
                }
            }
        }
        if (HasAnswer) {
            Console.WriteLine(Answer);
        }
        else {
            Console.WriteLine(-1);
        }
    }

    struct JyoutaiDef
    {
        internal long CurrNode; // 現在ノード
        internal long Cost;
    }
}

解説

コストが0と1なので、01BFSしてます。
最短コスト[ノード]での枝切りもしてます。

ノードXへの経路で、
コスト0のノードを100本経由する場合と
コスト1のノードを1本経由する場合の
2つを考えると、再訪防止のBFSを行うのはダメで、
最短コスト[ノード]での枝切りなら良いと分かります。