using System; using System.Text; using System.Linq; using System.Collections.Generic; public class Program { public void Proc() { Reader.IsDebug = false; int[] inpt = Reader.ReadLine().Split(' ').Select(a=>int.Parse(a)).ToArray(); this.Map = new int[inpt[0]]; this.Tax = new long[inpt[0]]; this.TimeLimit = inpt[1]; for(int i=0; iint.Parse(a)).ToArray(); int[][] posList = new int[][]{new int[]{inpt[0], inpt[1]}, new int[]{inpt[1], inpt[0]}}; foreach(int[] pos in posList) { if(!this.Road.ContainsKey(pos[0])) { this.Road.Add(pos[0], new Dictionary()); } this.Road[pos[0]][pos[1]] = inpt[2]; } } this.Map[0] = 0; Queue que = new Queue(); que.Enqueue(0); while(que.Count > 0) { int idx = que.Dequeue(); if(!Road.ContainsKey(idx)) { continue; } foreach(int moveTo in Road[idx].Keys) { int next = Map[idx] + this.Road[idx][moveTo]; if(Map[moveTo] > next) { que.Enqueue(moveTo); Map[moveTo] = next; } } } Console.WriteLine(Math.Max(Tax[0], GetAns(0, new int[this.Map.Length], this.TimeLimit))); } private Dictionary>> dic = new Dictionary>>(); private long GetAns(int pos, int[] flags, int remain) { if(this.Map[pos] > remain) { return -1; } string key = string.Join(string.Empty, flags); if(!dic.ContainsKey(pos)) { dic.Add(pos, new Dictionary>()); } if(!dic[pos].ContainsKey(remain)) { dic[pos].Add(remain, new Dictionary()); } if(dic[pos][remain].ContainsKey(key)) { return dic[pos][remain][key]; } long ans = -1; if(pos == 0) { ans = 0; } long addTax = 0; if(flags[pos] == 0) { addTax = Tax[pos]; flags[pos] = 1; } foreach(int moveTo in this.Road[pos].Keys) { long ret = this.GetAns(moveTo, flags, remain - this.Road[pos][moveTo]); if(ret >= 0) { ret+=addTax; } ans = Math.Max(ans, ret); } if(addTax > 0) { flags[pos] = 0; } dic[pos][remain][key] = ans; return ans; } private int TimeLimit; private int[] Map; private Dictionary> Road = new Dictionary>(); private long[] Tax; public class Reader { public static bool IsDebug = true; private static System.IO.StringReader SReader; private static string InitText = @" 2 50 10 50 0 1 50 "; public static string ReadLine() { if(IsDebug) { if(SReader == null) { SReader = new System.IO.StringReader(InitText.Trim()); } return SReader.ReadLine(); } else { return Console.ReadLine(); } } } public static void Main(string[] args) { Program prg = new Program(); prg.Proc(); } }