using System; using System.Collections.Generic; using System.Linq; // https://yukicoder.me/problems/no/2565 class Program { static string InputPattern = "InputX"; static List GetInputList() { var WillReturn = new List(); if (InputPattern == "Input1") { WillReturn.Add("4 6"); WillReturn.Add("1 2"); WillReturn.Add("2 4"); WillReturn.Add("2 3"); WillReturn.Add("3 1"); WillReturn.Add("3 4"); WillReturn.Add("4 3"); //4 } else if (InputPattern == "Input2") { WillReturn.Add("3 3"); WillReturn.Add("1 2"); WillReturn.Add("3 1"); WillReturn.Add("2 1"); //-1 } else if (InputPattern == "Input3") { WillReturn.Add("7 12"); WillReturn.Add("1 2"); WillReturn.Add("1 4"); WillReturn.Add("1 5"); WillReturn.Add("2 5"); WillReturn.Add("3 1"); WillReturn.Add("3 2"); WillReturn.Add("4 1"); WillReturn.Add("4 6"); WillReturn.Add("5 1"); WillReturn.Add("5 6"); WillReturn.Add("6 7"); WillReturn.Add("7 3"); //5 } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } static int mN; // 隣接リスト static Dictionary> mToNodeListDict = new Dictionary>(); static void Main() { List InputList = GetInputList(); int[] wkArr = { }; Action 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(); } mToNodeListDict[FromNode].Add(ToNode); } var AnswerList = new List(); bool Result1, Result2, Result3; int Cost1 = ExecBFS(out Result1, 1, 3); int Cost2 = ExecBFS(out Result2, 3, 4); int Cost3 = ExecBFS(out Result3, 4, 1); if (Result1 && Result2 && Result3) { AnswerList.Add(Cost1 + Cost2 + Cost3); } Cost1 = ExecBFS(out Result1, 1, 4); Cost2 = ExecBFS(out Result2, 4, 3); Cost3 = ExecBFS(out Result3, 3, 1); if (Result1 && Result2 && Result3) { AnswerList.Add(Cost1 + Cost2 + Cost3); } if (AnswerList.Count > 0) { Console.WriteLine(AnswerList.Min()); } else { Console.WriteLine(-1); } } // 始点と終点を引数として、コストを返す static int ExecBFS(out bool pHasAnswer, int pStaNode, int pGoalNode) { //Console.WriteLine("pStaNode={0},pGoalNode={1}", pStaNode, pGoalNode); pHasAnswer = false; var VisitedSet = new HashSet(); VisitedSet.Add(pStaNode); var Que = new Queue(); JyoutaiDef WillEnqueue; WillEnqueue.CurrNode = pStaNode; WillEnqueue.Level = 0; Que.Enqueue(WillEnqueue); while (Que.Count > 0) { JyoutaiDef Dequeued = Que.Dequeue(); //Console.WriteLine("CurrNode={0}", Dequeued.CurrNode); if (Dequeued.CurrNode == pGoalNode) { pHasAnswer = true; return Dequeued.Level; } if (mToNodeListDict.ContainsKey(Dequeued.CurrNode)) { foreach (int EachToNode in mToNodeListDict[Dequeued.CurrNode]) { if (VisitedSet.Add(EachToNode)) { WillEnqueue.CurrNode = EachToNode; WillEnqueue.Level = Dequeued.Level + 1; Que.Enqueue(WillEnqueue); } } } } return int.MaxValue; } struct JyoutaiDef { internal int CurrNode; internal int Level; } }