ABC257-F Teleporter Setting

問題へのリンク

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

    static int mN;

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

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

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

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

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

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

        var ResultBFSSei = ExecBFS(1);
        var ResultBFSRev = ExecBFS(mN);

        var AnswerList = new List<int>();

        for (int I = 1; I <= mN; I++) {
            var KouhoLost = new List<int>();

            // ワープを使わない場合
            if (ResultBFSSei.ContainsKey(mN)) {
                KouhoLost.Add(ResultBFSSei[mN]);
            }

            // ワープを使う場合その1
            if (ResultBFSSei.ContainsKey(0)) {
                if (ResultBFSRev.ContainsKey(I)) {
                    KouhoLost.Add(ResultBFSSei[0] + ResultBFSRev[I]);
                }
            }

            // ワープを使う場合その2
            if (ResultBFSRev.ContainsKey(0)) {
                if (ResultBFSSei.ContainsKey(I)) {
                    KouhoLost.Add(ResultBFSRev[0] + ResultBFSSei[I]);
                }
            }

            if (KouhoLost.Count > 0) {
                AnswerList.Add(KouhoLost.Min());
            }
            else {
                AnswerList.Add(-1);
            }
        }

        // セパレータとInt型の列挙を引数として、結合したstringを返す
        Func<string, IEnumerable<int>, string> IntEnumJoin = (pSeparater, pEnum) =>
        {
            string[] StrArr = Array.ConvertAll(pEnum.ToArray(), pX => pX.ToString());
            return string.Join(pSeparater, StrArr);
        };

        Console.WriteLine(IntEnumJoin(" ", AnswerList));
    }

    struct JyoutaiDef
    {
        internal int CurrNode; // 現在ノード
        internal int Level;
    }

    // BFSで、指定ノードから各ノードまでのコストを求める
    static Dictionary<int, int> ExecBFS(int pStaNode)
    {
        // コスト[ノード]なDict
        var WillReturn = new Dictionary<int, int>();

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.CurrNode = pStaNode;
        WillEnqueue.Level = 0;
        Que.Enqueue(WillEnqueue);

        WillReturn[pStaNode] = 0;

        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();

            if (mToNodeListDict.ContainsKey(Dequeued.CurrNode)) {
                foreach (int EachToNode in mToNodeListDict[Dequeued.CurrNode]) {
                    if (WillReturn.ContainsKey(EachToNode)) continue;

                    WillEnqueue.CurrNode = EachToNode;
                    WillEnqueue.Level = Dequeued.Level + 1;
                    Que.Enqueue(WillEnqueue);
                    WillReturn[EachToNode] = WillEnqueue.Level;
                }
            }
        }
        return WillReturn;
    }
}

解説

気付きとして、ワープを2回以上するので無駄で
ワープ回数は0回か1回です。

最初にノード1から各ノードまでの最短距離を求めます。

双方向探索の感覚で
ゴールノードから各ノードまでの最短距離も求めます。

経路は、ノード0を使う場合と、使わない場合の2通りなので
場合に分けて考えると

解候補は、
●開始ノードからゴールノードまで、ノード0を経由しない経路
●開始ノードからノード0に移動してから、ゴールノードに移動する経路
●双方向探索の感覚で、ゴールノードからノード0に移動してから、開始ノードに移動する経路
の3つなので、これらの最短距離を求めてます。