結果
問題 | No.1 道のショートカット |
ユーザー | 明智重蔵 |
提出日時 | 2015-09-19 06:38:25 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 1,291 ms / 5,000 ms |
コード長 | 4,568 bytes |
コンパイル時間 | 3,656 ms |
コンパイル使用メモリ | 108,328 KB |
実行使用メモリ | 28,608 KB |
最終ジャッジ日時 | 2023-09-27 21:48:33 |
合計ジャッジ時間 | 10,324 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 68 ms
21,860 KB |
testcase_01 | AC | 70 ms
22,024 KB |
testcase_02 | AC | 67 ms
23,920 KB |
testcase_03 | AC | 62 ms
21,964 KB |
testcase_04 | AC | 64 ms
21,936 KB |
testcase_05 | AC | 68 ms
23,952 KB |
testcase_06 | AC | 65 ms
20,040 KB |
testcase_07 | AC | 64 ms
19,892 KB |
testcase_08 | AC | 91 ms
28,384 KB |
testcase_09 | AC | 74 ms
24,128 KB |
testcase_10 | AC | 94 ms
28,356 KB |
testcase_11 | AC | 180 ms
26,360 KB |
testcase_12 | AC | 227 ms
28,608 KB |
testcase_13 | AC | 224 ms
26,492 KB |
testcase_14 | AC | 70 ms
24,004 KB |
testcase_15 | AC | 60 ms
21,876 KB |
testcase_16 | AC | 73 ms
24,212 KB |
testcase_17 | AC | 66 ms
23,932 KB |
testcase_18 | AC | 66 ms
21,976 KB |
testcase_19 | AC | 69 ms
22,036 KB |
testcase_20 | AC | 82 ms
24,188 KB |
testcase_21 | AC | 76 ms
22,096 KB |
testcase_22 | AC | 66 ms
21,956 KB |
testcase_23 | AC | 1,240 ms
26,252 KB |
testcase_24 | AC | 1,291 ms
28,412 KB |
testcase_25 | AC | 106 ms
26,268 KB |
testcase_26 | AC | 91 ms
28,552 KB |
testcase_27 | AC | 363 ms
26,348 KB |
testcase_28 | AC | 63 ms
21,944 KB |
testcase_29 | AC | 121 ms
28,228 KB |
testcase_30 | AC | 78 ms
24,152 KB |
testcase_31 | AC | 116 ms
28,248 KB |
testcase_32 | AC | 106 ms
26,292 KB |
testcase_33 | AC | 90 ms
28,252 KB |
testcase_34 | AC | 283 ms
28,264 KB |
testcase_35 | AC | 74 ms
22,232 KB |
testcase_36 | AC | 84 ms
24,232 KB |
testcase_37 | AC | 75 ms
22,044 KB |
testcase_38 | AC | 67 ms
22,008 KB |
testcase_39 | AC | 73 ms
20,024 KB |
testcase_40 | AC | 72 ms
22,176 KB |
testcase_41 | AC | 74 ms
22,140 KB |
testcase_42 | AC | 63 ms
23,988 KB |
testcase_43 | AC | 61 ms
23,716 KB |
コンパイルメッセージ
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 = "Input4"; 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); } }