結果
問題 | No.1 道のショートカット |
ユーザー |
![]() |
提出日時 | 2024-10-10 21:25:12 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 1,425 ms / 5,000 ms |
コード長 | 4,569 bytes |
コンパイル時間 | 1,127 ms |
コンパイル使用メモリ | 114,896 KB |
実行使用メモリ | 32,276 KB |
最終ジャッジ日時 | 2024-10-10 21:25:22 |
合計ジャッジ時間 | 8,479 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections.Generic; using System.Linq; class Program { static string InputPattern = "InputX"; static List<string> GetInputList() { var WillReturn = new List<string>(); if (InputPattern == "Input1") { WillReturn.Add("3"); WillReturn.Add("100"); WillReturn.Add("3"); WillReturn.Add("1 2 1"); WillReturn.Add("2 3 3"); WillReturn.Add("10 90 10"); WillReturn.Add("10 10 50"); //20 //1→3 と行くと コスト10だが、単位時間が50掛かる。 //1→2→3 と行くと 一文無しになるが、20単位時間なので早いのでこちらを選択する。 } else if (InputPattern == "Input2") { WillReturn.Add("3"); WillReturn.Add("100"); WillReturn.Add("3"); WillReturn.Add("1 2 1"); WillReturn.Add("2 3 3"); WillReturn.Add("1 100 10"); WillReturn.Add("10 10 50"); //50 //1→2→3 と行くと時間は20と短いが、コスト101かかるため選択できない。 } else if (InputPattern == "Input3") { WillReturn.Add("10"); WillReturn.Add("10"); WillReturn.Add("19"); WillReturn.Add("1 1 2 4 5 1 3 4 6 4 6 4 5 7 8 2 3 4 9"); WillReturn.Add("3 5 5 5 6 7 7 7 7 8 8 9 9 9 9 10 10 10 10"); WillReturn.Add("8 6 8 7 6 6 9 9 7 6 9 7 7 8 7 6 6 8 6"); WillReturn.Add("8 9 10 4 10 3 5 9 3 4 1 8 3 1 3 6 6 10 4"); //-1 } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } struct JyoutaiDef { internal int CurrPos; internal int SumC; internal int SumM; internal string Path; } static void Main() { List<string> InputList = GetInputList(); int N = int.Parse(InputList[0]); int C = int.Parse(InputList[1]); int[] SArr = InputList[3].Split(' ').Select(X => int.Parse(X)).ToArray(); int[] TArr = InputList[4].Split(' ').Select(X => int.Parse(X)).ToArray(); int[] YArr = InputList[5].Split(' ').Select(X => int.Parse(X)).ToArray(); int[] MArr = InputList[6].Split(' ').Select(X => int.Parse(X)).ToArray(); int UB = SArr.GetUpperBound(0); var stk = new Stack<JyoutaiDef>(); JyoutaiDef WillPush; WillPush.CurrPos = 1; WillPush.SumC = WillPush.SumM = 0; WillPush.Path = "1"; stk.Push(WillPush); //SumM[SumC]なDictの配列(ノード番号を添字とする) var MemoDictArr = new Dictionary<int, int>[N + 1]; for (int I = 1; I <= N; I++) { MemoDictArr[I] = new Dictionary<int, int>(); } bool HasAnswer = false; string AnswerPath = ""; int AnswerSumM = int.MaxValue; while (stk.Count > 0) { JyoutaiDef Popped = stk.Pop(); //クリア処理 if (Popped.CurrPos == N) { HasAnswer = true; if (AnswerSumM > Popped.SumM) { AnswerSumM = Popped.SumM; AnswerPath = Popped.Path; //Console.WriteLine("解候補{0}を発見", Popped.Path); } continue; } for (int I = 0; I <= UB; I++) { if (Popped.CurrPos != SArr[I]) continue; WillPush.CurrPos = TArr[I]; WillPush.SumC = Popped.SumC + YArr[I]; WillPush.SumM = Popped.SumM + MArr[I]; WillPush.Path = Popped.Path + string.Format(",{0}", TArr[I]); if (WillPush.SumC > C) continue; if (MemoDictArr[WillPush.CurrPos].ContainsKey(WillPush.SumC)) { if (MemoDictArr[WillPush.CurrPos][WillPush.SumC] < WillPush.SumM) { continue; } } MemoDictArr[WillPush.CurrPos][WillPush.SumC] = WillPush.SumM; stk.Push(WillPush); } } if (HasAnswer) { //Console.WriteLine(new string('■', 15)); //Console.WriteLine("解を発見"); Console.WriteLine(AnswerSumM); //Console.WriteLine("経路は{0}", AnswerPath); } else Console.WriteLine(-1); } }