using System; using System.Collections.Generic; using System.Linq; class Program { static string InputPattern = "InputX"; static List GetInputList() { var WillReturn = new List(); if (InputPattern == "Input1") { WillReturn.Add("13 13"); WillReturn.Add("1 2"); WillReturn.Add("2 3"); WillReturn.Add("3 4"); WillReturn.Add("4 5"); WillReturn.Add("5 6"); WillReturn.Add("6 13"); WillReturn.Add("1 7"); WillReturn.Add("7 8"); WillReturn.Add("8 9"); WillReturn.Add("9 10"); WillReturn.Add("9 12"); WillReturn.Add("10 11"); WillReturn.Add("11 13"); WillReturn.Add("10"); WillReturn.Add("2 3 4 5 6 7 8 9 10 11"); //8 } else if (InputPattern == "Input2") { WillReturn.Add("7 6"); WillReturn.Add("1 2"); WillReturn.Add("2 3"); WillReturn.Add("3 4"); WillReturn.Add("4 5"); WillReturn.Add("5 6"); WillReturn.Add("6 7"); WillReturn.Add("5"); WillReturn.Add("2 3 4 5 6"); //-1 } else if (InputPattern == "Input3") { WillReturn.Add("3 2"); WillReturn.Add("1 2"); WillReturn.Add("2 3"); WillReturn.Add("0"); //2 } 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 HashSet mKSet = new HashSet(); // 隣接リスト static Dictionary> mToNodeListDict = new Dictionary>(); static long mN; static void Main() { List InputList = GetInputList(); long[] wkArr = { }; Action SplitAct = (pStr) => wkArr = GetSplitArr(pStr); SplitAct(InputList[0]); mN=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(); } if (mToNodeListDict.ContainsKey(ToNode) == false) { mToNodeListDict[ToNode] = new List(); } mToNodeListDict[FromNode].Add(ToNode); mToNodeListDict[ToNode].Add(FromNode); } long K = long.Parse(InputList[(int)M + 1]); if (K >= 1) { SplitAct(InputList.Last()); mKSet.UnionWith(wkArr); } var Que = new Queue(); JyoutaiDef WillEnqueue; WillEnqueue.CurrNode = 1; WillEnqueue.IwaiCnt = 0; WillEnqueue.Cost = 0; Que.Enqueue(WillEnqueue); long Answer = long.MaxValue; bool HasAnswer = false; // 最小コスト[ハッシュ] var EadakiriDict = new Dictionary(); while (Que.Count > 0) { JyoutaiDef Dequeued=Que.Dequeue(); // クリア判定 if (Dequeued.CurrNode == mN) { HasAnswer = true; Answer = Math.Min(Answer, Dequeued.Cost); continue; } if (HasAnswer) { if (Answer <= Dequeued.Cost) continue; } foreach (long EachToNode in mToNodeListDict[Dequeued.CurrNode]) { WillEnqueue.CurrNode = EachToNode; WillEnqueue.IwaiCnt = Dequeued.IwaiCnt; if (mKSet.Contains(EachToNode)) { WillEnqueue.IwaiCnt++; } else { WillEnqueue.IwaiCnt = 0; } if (WillEnqueue.IwaiCnt == 5) continue; WillEnqueue.Cost = Dequeued.Cost + 1; long Hash = GetHash(EachToNode, WillEnqueue.IwaiCnt); if (EadakiriDict.ContainsKey(Hash)) { if (EadakiriDict[Hash] <= WillEnqueue.Cost) { continue; } } EadakiriDict[Hash] = WillEnqueue.Cost; Que.Enqueue(WillEnqueue); } } if (HasAnswer) { Console.WriteLine(Answer); } else { Console.WriteLine(-1); } } static long GetHash(long pNode, long pIwaiCnt) { return pNode * 10 + pIwaiCnt; } struct JyoutaiDef { internal long CurrNode; internal long IwaiCnt; internal long Cost; } }