ABC197-F Construct a Palindrome

問題へのリンク

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

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

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

        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long N = wkArr[0];

        foreach (string EachStr in InputList.Skip(1)) {
            string[] SplitArr = EachStr.Split(' ');

            long FromNode = long.Parse(SplitArr[0]);
            long ToNode = long.Parse(SplitArr[1]);
            char Moji = SplitArr[2][0];

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

            // 逆辺も作る
            if (mEdgeInfoListDict.ContainsKey(ToNode) == false) {
                mEdgeInfoListDict[ToNode] = new List<EdgeInfoDef>();
            }
            EdgeInfoDef WillAdd2;
            WillAdd2.ToNode = FromNode;
            WillAdd2.Moji = Moji;
            mEdgeInfoListDict[ToNode].Add(WillAdd2);
        }

        long Answer = DeriveAnswer(1, N);
        Console.WriteLine(Answer);
    }

    // FromNodeとToNodeを引数として、解を返す
    static long DeriveAnswer(long pFromNode, long pToNode)
    {
        if (pFromNode == pToNode) {
            return 0;
        }

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnq;
        WillEnq.Node1 = pFromNode;
        WillEnq.Node2 = pToNode;
        WillEnq.Level = 0;

        Que.Enqueue(WillEnq);

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

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

            if (Deq.Node1 == Deq.Node2) {
                HasAnswer = true;
                Answer = Math.Min(Answer, Deq.Level);
                continue;
            }

            bool WillContinue = false;
            if (mEdgeInfoListDict.ContainsKey(Deq.Node1)) {
                foreach (EdgeInfoDef EachEdge1 in mEdgeInfoListDict[Deq.Node1]) {
                    if (EachEdge1.ToNode == Deq.Node2) {
                        HasAnswer = true;
                        Answer = Math.Min(Answer, Deq.Level + 1);
                        WillContinue = true;
                    }
                }
            }
            if (WillContinue) continue;

            if (Answer <= Deq.Level) continue;

            if (mEdgeInfoListDict.ContainsKey(Deq.Node1) && mEdgeInfoListDict.ContainsKey(Deq.Node2)) {
                foreach (EdgeInfoDef EachEdge1 in mEdgeInfoListDict[Deq.Node1]) {
                    foreach (EdgeInfoDef EachEdge2 in mEdgeInfoListDict[Deq.Node2]) {
                        if (EachEdge1.Moji != EachEdge2.Moji) {
                            continue;
                        }
                        long NewNode1 = EachEdge1.ToNode;
                        long NewNode2 = EachEdge2.ToNode;
                        long Hash = GetHash(NewNode1, NewNode2);
                        if (VisitedSet.Add(Hash)) {
                            WillEnq.Node1 = NewNode1;
                            WillEnq.Node2 = NewNode2;
                            WillEnq.Level = Deq.Level + 2;
                            Que.Enqueue(WillEnq);
                        }
                    }
                }
            }
        }

        if (HasAnswer == false) {
            return -1;
        }
        else {
            return Answer;
        }
    }

    static long GetHash(long pNode1, long pNode2)
    {
        long Hash = pNode1 * 10000 + pNode2;
        return Hash;
    }

    struct JyoutaiDef
    {
        internal long Node1;
        internal long Node2;
        internal long Level;
    }
}

解説

始点と終点から双方向探索してます。