結果

問題 No.17 2つの地点に泊まりたい
ユーザー 明智重蔵明智重蔵
提出日時 2015-10-24 03:44:15
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 7,522 bytes
コンパイル時間 2,348 ms
コンパイル使用メモリ 118,752 KB
実行使用メモリ 32,152 KB
最終ジャッジ日時 2024-09-13 04:49:14
合計ジャッジ時間 16,707 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
25,516 KB
testcase_01 AC 43 ms
25,804 KB
testcase_02 AC 42 ms
25,176 KB
testcase_03 AC 44 ms
29,416 KB
testcase_04 AC 55 ms
29,544 KB
testcase_05 AC 472 ms
31,844 KB
testcase_06 AC 381 ms
27,512 KB
testcase_07 AC 314 ms
31,712 KB
testcase_08 AC 3,037 ms
32,152 KB
testcase_09 AC 2,520 ms
29,984 KB
testcase_10 AC 168 ms
31,724 KB
testcase_11 AC 315 ms
31,960 KB
testcase_12 AC 41 ms
27,588 KB
testcase_13 AC 42 ms
25,372 KB
testcase_14 AC 43 ms
27,472 KB
testcase_15 AC 42 ms
25,368 KB
testcase_16 AC 41 ms
25,628 KB
testcase_17 AC 43 ms
27,356 KB
testcase_18 AC 46 ms
27,364 KB
testcase_19 AC 42 ms
27,728 KB
testcase_20 AC 42 ms
25,500 KB
testcase_21 AC 42 ms
27,224 KB
testcase_22 AC 45 ms
27,624 KB
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        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<int> SyukuhakuIndList;
        //internal string Path;
    }

    struct MemoInfoDef
    {
        internal int MoveCost;
        internal int SyukuhakuCost;
    }

    //17 2つの地点に泊まりたい
    static void Main()
    {
        List<string> InputList = GetInputList();
        int N = int.Parse(InputList[0]);

        var SList = new List<int>();
        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>();
        JyoutaiDef WillPush;
        WillPush.CurrPos = 0;
        WillPush.MoveCost = 0;
        WillPush.SyukuhakuIndList = new List<int>();
        //WillPush.Path = "0,";
        stk.Push(WillPush);

        //コスト情報のList[移動先ノード,宿の数]なメモの配列
        var MemoListArr = new List<MemoInfoDef>[N, 2 + 1];
        for (int I = 0; I <= MemoListArr.GetUpperBound(0); I++)
            for (int J = 0; J <= MemoListArr.GetUpperBound(1); J++)
                MemoListArr[I, J] = new List<MemoInfoDef>();

        int Answer = int.MaxValue;

        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();
            //Console.WriteLine(Popped.Path);

            //クリア判定
            if (Popped.CurrPos == N - 1
             && Popped.SyukuhakuIndList.Count == 2) {
                //Console.WriteLine("解候補を発見");
                //Console.WriteLine("SumCost={0}", Popped.SumCost);
                //Console.WriteLine("宿1は、ノード{0},宿泊コスト={1}",
                //    Popped.SyukuhakuIndList[0], SArr[Popped.SyukuhakuIndList[0]]);
                //Console.WriteLine("宿2は、ノード{0},宿泊コスト={1}",
                //    Popped.SyukuhakuIndList[1], SArr[Popped.SyukuhakuIndList[1]]);
                //Console.WriteLine("Path={0}", Popped.Path);

                int CurrCost = Popped.MoveCost + Popped.SyukuhakuIndList.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.SyukuhakuIndList = Popped.SyukuhakuIndList;

                //宿泊コストの更新処理
                if (0 < LoopY && LoopY < N - 1
                 && Popped.SyukuhakuIndList.Contains(LoopY) == false) {

                    int NewSyukuhakuCost = SArr[LoopY];

                    if (Popped.SyukuhakuIndList.Count <= 1
                     || NewSyukuhakuCost < Popped.SyukuhakuIndList.Max(X => SArr[X])) {
                        WillPush.SyukuhakuIndList = new List<int>(Popped.SyukuhakuIndList);
                        WillPush.SyukuhakuIndList.Add(LoopY);
                        WillPush.SyukuhakuIndList =
                           WillPush.SyukuhakuIndList.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 MoveCost = WillPush.MoveCost;
                int SyukuhakuCost = WillPush.SyukuhakuIndList.Sum(X => SArr[X]);
                int SyukuhakuCnt = WillPush.SyukuhakuIndList.Count;

                if (MemoListArr[WillPush.CurrPos, SyukuhakuCnt].Exists(X =>
                    X.MoveCost <= MoveCost && X.SyukuhakuCost <= SyukuhakuCost)) {
                    continue;
                }
                MemoInfoDef WillAdd;
                WillAdd.MoveCost = MoveCost;
                WillAdd.SyukuhakuCost = SyukuhakuCost;
                MemoListArr[WillPush.CurrPos, SyukuhakuCnt].Add(WillAdd);

                //下限値枝切り
                if (Answer <= MoveCost) continue;

                stk.Push(WillPush);
            }
        }
        Console.WriteLine(Answer);
    }
}
0