ABC429-E Hit and Away

問題へのリンク

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("5 5");
            WillReturn.Add("1 2");
            WillReturn.Add("1 3");
            WillReturn.Add("2 3");
            WillReturn.Add("3 4");
            WillReturn.Add("4 5");
            WillReturn.Add("SSDDS");
            //2
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3 2");
            WillReturn.Add("1 2");
            WillReturn.Add("2 3");
            WillReturn.Add("SSD");
            //3
        }
        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 = { };
        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);
        }

        char[] SArr = InputList.Last().ToCharArray();

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        for (long I = 0; I <= SArr.GetUpperBound(0); I++) {
            if (SArr[I] == 'S') {
                WillEnqueue.StaNode = I + 1;
                WillEnqueue.CurrNode = I + 1;
                WillEnqueue.Level = 0;
                Que.Enqueue(WillEnqueue);
            }
        }

        var EdakiriListDict = new Dictionary<long, List<EdakiriInfoDef>>();
        for (long I = 1; I <= N; I++) {
            EdakiriListDict[I] = new List<EdakiriInfoDef>();
        }

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

            long CurrNode = Dequeued.CurrNode;

            // 枝切り
            if (EdakiriListDict[CurrNode].Count < 2) {
                if (EdakiriListDict[CurrNode].Exists(pX => pX.StaNode == Dequeued.StaNode)) {
                    continue;
                }

                EdakiriInfoDef WillAdd;
                WillAdd.StaNode = Dequeued.StaNode;
                WillAdd.Level = Dequeued.Level;
                EdakiriListDict[CurrNode].Add(WillAdd);
            }
            else {
                continue;
            }

            foreach (long EachToNode in mToNodeListDict[CurrNode]) {
                WillEnqueue.StaNode = Dequeued.StaNode;
                WillEnqueue.CurrNode = EachToNode;
                WillEnqueue.Level = Dequeued.Level + 1;
                Que.Enqueue(WillEnqueue);
            }
        }

        for (long I = 0; I <= SArr.GetUpperBound(0); I++) {
            if (SArr[I] == 'D') {
                long Answer = EdakiriListDict[I + 1].Sum(pX => pX.Level);
                Console.WriteLine(Answer);
            }
        }
    }

    struct JyoutaiDef
    {
        internal long StaNode;
        internal long CurrNode;
        internal long Level;
    }

    struct EdakiriInfoDef
    {
        internal long StaNode;
        internal long Level;
    }
}

解説

ダイソーのオセロセットで
下記の盤面で4近傍への辺があると考え、多始点BFSしてます。

　○
○●●●●●●●
　○　●　●　●
　○　○　●　○

距離の短い順でTop2まで必要なので
Top3以降は枝切りしてます。