結果

問題 No.1 道のショートカット
ユーザー 明智重蔵明智重蔵
提出日時 2015-09-12 10:42:50
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 4,923 bytes
コンパイル時間 1,215 ms
コンパイル使用メモリ 115,152 KB
実行使用メモリ 39,216 KB
最終ジャッジ日時 2024-07-08 04:13:05
合計ジャッジ時間 9,336 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 32 ms
27,472 KB
testcase_01 AC 32 ms
19,200 KB
testcase_02 AC 32 ms
19,328 KB
testcase_03 AC 33 ms
19,200 KB
testcase_04 AC 33 ms
19,328 KB
testcase_05 AC 32 ms
19,200 KB
testcase_06 AC 32 ms
19,328 KB
testcase_07 AC 32 ms
19,200 KB
testcase_08 AC 307 ms
23,496 KB
testcase_09 AC 41 ms
19,968 KB
testcase_10 AC 724 ms
23,612 KB
testcase_11 TLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

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;
    }

    struct MemoInfo
    {
        internal int Pos;
        internal int MinSumC;
        internal int MinSumM;
    }

    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);

        var MemoList = new List<MemoInfo>();
        MemoList.Add(new MemoInfo() { Pos = 1, MinSumC = 0, MinSumM = 0 });

        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 (MemoList.Exists(A => A.Pos == WillPush.CurrPos
                                      && A.MinSumC <= WillPush.SumC
                                      && A.MinSumM <= WillPush.SumM))
                    continue;

                MemoInfo WillAdd;
                WillAdd.Pos = I;
                WillAdd.MinSumC = WillPush.SumC;
                WillAdd.MinSumM = WillPush.SumM;

                //無駄なメモをRemoveしてからAdd
                //MemoList.RemoveAll(A => A.Pos == I
                //                     && A.MinSumC >= WillAdd.MinSumC
                //                     && A.MinSumM >= WillAdd.MinSumM);
                MemoList.Add(WillAdd);

                stk.Push(WillPush);
            }
        }
        if (HasAnswer) {
            //Console.WriteLine(new string('■', 15));
            //Console.WriteLine("解を発見");
            Console.WriteLine(AnswerSumM);
            //Console.WriteLine("経路は{0}", AnswerPath);
        }
        else Console.WriteLine(-1);
    }
}
0