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("4"); WillReturn.Add("0"); WillReturn.Add("2"); WillReturn.Add("100"); WillReturn.Add("0"); WillReturn.Add("5"); WillReturn.Add("0 1 1"); WillReturn.Add("0 2 1"); WillReturn.Add("1 2 1"); WillReturn.Add("1 3 1"); WillReturn.Add("2 3 2"); //105 //地点は全部で4個。 //地点1と地点2にはかならず滞在しなけらばならない。 //0→2→1→3 の順番で移動し、 //地点1と地点2に滞在したとき最小コストになる。 } else if (InputPattern == "Input2") { WillReturn.Add("4"); WillReturn.Add("0"); WillReturn.Add("3"); WillReturn.Add("3"); WillReturn.Add("0"); WillReturn.Add("3"); WillReturn.Add("0 1 1"); WillReturn.Add("1 3 2"); WillReturn.Add("2 3 4"); //17 //地点1と地点2にはかならず滞在しなけらばならない。 //よって、0→1→3→2→3 のような移動が必要。 //同じ地点を2度通っても良い。 } else if (InputPattern == "Input3") { WillReturn.Add("16"); WillReturn.Add("0"); WillReturn.Add("15"); WillReturn.Add("6"); WillReturn.Add("23"); WillReturn.Add("8"); WillReturn.Add("193"); WillReturn.Add("14"); WillReturn.Add("13"); WillReturn.Add("53"); WillReturn.Add("16"); WillReturn.Add("85"); WillReturn.Add("12"); WillReturn.Add("15"); WillReturn.Add("5"); WillReturn.Add("14"); WillReturn.Add("0"); WillReturn.Add("15"); WillReturn.Add("0 1 17"); WillReturn.Add("14 15 18"); WillReturn.Add("7 8 87"); WillReturn.Add("4 5 137"); WillReturn.Add("8 9 17"); WillReturn.Add("11 12 33"); WillReturn.Add("5 6 177"); WillReturn.Add("9 10 47"); WillReturn.Add("10 11 27"); WillReturn.Add("1 2 77"); WillReturn.Add("6 7 114"); WillReturn.Add("12 13 15"); WillReturn.Add("2 3 127"); WillReturn.Add("13 14 11"); WillReturn.Add("3 4 85"); //1000 } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } struct JyoutaiDef { internal int CurrPos; internal int MoveCost; internal List SyokuhakuIndList; //internal string Path; } //17 2つの地点に泊まりたい //http://yukicoder.me/problems/61 static void Main() { List InputList = GetInputList(); int N = int.Parse(InputList[0]); var SList = new List(); foreach (string EachStr in InputList.Skip(1).Take(N)) { SList.Add(int.Parse(EachStr)); } int[] SArr = SList.ToArray(); //隣接行列でエッジを表現 int[,] RinsetuGyouretu = new int[N, N]; foreach (string EachStr in InputList.Skip(1 + N + 1)) { int[] wkArr = EachStr.Split(' ').Select(X => int.Parse(X)).ToArray(); RinsetuGyouretu[wkArr[0], wkArr[1]] = wkArr[2]; RinsetuGyouretu[wkArr[1], wkArr[0]] = wkArr[2]; } var stk = new Stack(); JyoutaiDef WillPush; WillPush.CurrPos = 0; WillPush.MoveCost = 0; WillPush.SyokuhakuIndList = new List(); //WillPush.Path = "0,"; stk.Push(WillPush); //最小コスト[移動先ノード][宿の数]なメモ Nullable[,] MemoArr = new Nullable[N, 2 + 1]; int Answer = int.MaxValue; while (stk.Count > 0) { JyoutaiDef Popped = stk.Pop(); //Console.WriteLine(Popped.Path); //クリア判定 if (Popped.CurrPos == N - 1 && Popped.SyokuhakuIndList.Count == 2) { //Console.WriteLine("解候補を発見"); //Console.WriteLine("SumCost={0}", Popped.SumCost); //Console.WriteLine("宿1は、ノード{0},宿泊コスト={1}", // Popped.SyokuhakuIndList[0], SArr[Popped.SyokuhakuIndList[0]]); //Console.WriteLine("宿2は、ノード{0},宿泊コスト={1}", // Popped.SyokuhakuIndList[1], SArr[Popped.SyokuhakuIndList[1]]); //Console.WriteLine("Path={0}", Popped.Path); int CurrCost = Popped.MoveCost + Popped.SyokuhakuIndList.Sum(X => SArr[X]); if (Answer > CurrCost) Answer = CurrCost; continue; } for (int LoopY = 0; LoopY <= N - 1; LoopY++) { if (RinsetuGyouretu[Popped.CurrPos, LoopY] == 0) continue; WillPush.SyokuhakuIndList = Popped.SyokuhakuIndList; //宿泊コストの更新処理 if (0 < LoopY && LoopY < N - 1) { if (Popped.SyokuhakuIndList.Contains(LoopY)) continue; int NewSyokuhakuCost = SArr[LoopY]; if (Popped.SyokuhakuIndList.Count <= 1 || NewSyokuhakuCost < Popped.SyokuhakuIndList.Min(X => SArr[X])) { WillPush.SyokuhakuIndList = new List(Popped.SyokuhakuIndList); WillPush.SyokuhakuIndList.Add(LoopY); WillPush.SyokuhakuIndList = WillPush.SyokuhakuIndList.OrderBy(X => SArr[X]).Take(2).ToList(); } } WillPush.CurrPos = LoopY; WillPush.MoveCost = Popped.MoveCost + RinsetuGyouretu[Popped.CurrPos, LoopY]; //WillPush.Path = Popped.Path + LoopY.ToString() + ","; //メモ化探索 int SumCost = WillPush.MoveCost + WillPush.SyokuhakuIndList.Sum(X => SArr[X]); int SyokuhakuCount = WillPush.SyokuhakuIndList.Count; if (MemoArr[WillPush.CurrPos, SyokuhakuCount] != null) { if (MemoArr[WillPush.CurrPos, SyokuhakuCount].Value <= SumCost) continue; } MemoArr[WillPush.CurrPos, SyokuhakuCount] = SumCost; //下限値枝切り if (Answer <= SumCost) continue; stk.Push(WillPush); } } Console.WriteLine(Answer); } }