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("3 2 2"); WillReturn.Add("1 2 10"); WillReturn.Add("2 3 20"); WillReturn.Add("10 20"); //1 //3 //犯人は通行料金10の道路を通り、続いて通行料金20の道路を通った。 //ここから犯人は今町3にいると分かる。 } else if (InputPattern == "Input2") { WillReturn.Add("3 2 2"); WillReturn.Add("1 2 10"); WillReturn.Add("1 2 20"); WillReturn.Add("10 20"); //2 //1 2 //ある町のペアを複数本の道路が結ぶこともある。 //また、どの町のペアも互いに行き来できるとは限らない。 } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } static void Main() { List InputList = GetInputList(); int[] wkArr = { }; Action SplitAct = (pStr) => wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray(); SplitAct(InputList[0]); int N = wkArr[0]; int M = wkArr[1]; //隣接行列のListでグラフを定義 var RinsetuGyouretuListArr = new List[N + 1, N + 1]; foreach (string EachStr in InputList.Skip(1).Take(M)) { SplitAct(EachStr); if (RinsetuGyouretuListArr[wkArr[0], wkArr[1]] == null) RinsetuGyouretuListArr[wkArr[0], wkArr[1]] = new List(); if (RinsetuGyouretuListArr[wkArr[1], wkArr[0]] == null) RinsetuGyouretuListArr[wkArr[1], wkArr[0]] = new List(); RinsetuGyouretuListArr[wkArr[0], wkArr[1]].Add(wkArr[2]); RinsetuGyouretuListArr[wkArr[1], wkArr[0]].Add(wkArr[2]); } string wkStr = InputList.ElementAt(1 + M); int[] DArr = wkStr.Split(' ').Select(X => int.Parse(X)).ToArray(); //到達可否[町番号]なDP表 bool[] PrevDP = new bool[N + 1]; for (int I = 1; I <= PrevDP.GetUpperBound(0); I++) PrevDP[I] = true; foreach (int EachInt in DArr) { bool[] CurrDP = new bool[N + 1]; for (int I = 1; I <= PrevDP.GetUpperBound(0); I++) { if (PrevDP[I] == false) continue; for (int J = 1; J <= RinsetuGyouretuListArr.GetUpperBound(1); J++) { if (RinsetuGyouretuListArr[I, J] == null) continue; if (RinsetuGyouretuListArr[I, J].Contains(EachInt)) { CurrDP[J] = true; } } } PrevDP = CurrDP; } Console.WriteLine(PrevDP.Count(X => X)); var sb = new System.Text.StringBuilder(); for (int I = 1; I <= PrevDP.GetUpperBound(0); I++) { if (PrevDP[I]) sb.AppendFormat("{0} ", I); } Console.WriteLine(sb.ToString().TrimEnd()); } }