結果

問題 No.17 2つの地点に泊まりたい
ユーザー 明智重蔵明智重蔵
提出日時 2016-02-09 06:05:52
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 7,876 bytes
コンパイル時間 1,073 ms
コンパイル使用メモリ 116,428 KB
実行使用メモリ 34,848 KB
最終ジャッジ日時 2024-09-21 21:58:02
合計ジャッジ時間 20,688 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
25,520 KB
testcase_01 AC 43 ms
25,832 KB
testcase_02 AC 43 ms
27,412 KB
testcase_03 AC 47 ms
27,516 KB
testcase_04 AC 72 ms
31,472 KB
testcase_05 AC 905 ms
29,852 KB
testcase_06 AC 700 ms
29,580 KB
testcase_07 AC 431 ms
31,476 KB
testcase_08 AC 4,816 ms
32,944 KB
testcase_09 AC 3,861 ms
30,768 KB
testcase_10 AC 234 ms
31,724 KB
testcase_11 AC 441 ms
31,740 KB
testcase_12 AC 43 ms
25,248 KB
testcase_13 AC 43 ms
27,412 KB
testcase_14 AC 42 ms
25,376 KB
testcase_15 AC 45 ms
27,360 KB
testcase_16 AC 43 ms
25,368 KB
testcase_17 AC 43 ms
23,604 KB
testcase_18 AC 51 ms
31,756 KB
testcase_19 AC 44 ms
25,584 KB
testcase_20 AC 43 ms
25,244 KB
testcase_21 AC 43 ms
25,368 KB
testcase_22 AC 49 ms
27,400 KB
testcase_23 AC 761 ms
27,668 KB
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 SumSyukuhakuCost;
        internal int MinSyukuhakuCost;
    }

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

            //クリア判定
            if (Popped.CurrPos == N - 1
             && Popped.SyukuhakuIndList.Count == 2) {

                int SumCost = Popped.MoveCost + Popped.SyukuhakuIndList.Sum(X => SArr[X]);
                if (Answer > SumCost) {
                    Answer = SumCost;
                    //Console.WriteLine("解候補を発見");
                    //Console.WriteLine("SumCost={0}", 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);
                }
            }

            for (int LoopJ = 0; LoopJ <= N - 1; LoopJ++) {
                if (RinsetuGyouretu[Popped.CurrPos, LoopJ] == 0) continue;

                WillPush.SyukuhakuIndList = new List<int>(Popped.SyukuhakuIndList);

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

                    int NewSyukuhakuCost = SArr[LoopJ];

                    if (Popped.SyukuhakuIndList.Count <= 1
                     || NewSyukuhakuCost < Popped.SyukuhakuIndList.Max(X => SArr[X])) {
                        WillPush.SyukuhakuIndList = new List<int>(Popped.SyukuhakuIndList);
                        WillPush.SyukuhakuIndList.Add(LoopJ);
                        WillPush.SyukuhakuIndList =
                           WillPush.SyukuhakuIndList.OrderBy(X => SArr[X]).Take(2).ToList();
                    }
                }

                WillPush.CurrPos = LoopJ;
                WillPush.MoveCost = Popped.MoveCost + RinsetuGyouretu[Popped.CurrPos, LoopJ];
                WillPush.Path = Popped.Path + LoopJ.ToString() + ",";

                //メモ化探索
                int SyukuhakuCnt = WillPush.SyukuhakuIndList.Count;
                int MoveCost = WillPush.MoveCost;
                int SumSyukuhakuCost = 0;
                int MinSyukuhakuCost = 0;
                if (SyukuhakuCnt > 0) {
                    SumSyukuhakuCost = WillPush.SyukuhakuIndList.Sum(X => SArr[X]);
                    MinSyukuhakuCost = WillPush.SyukuhakuIndList.Min(X => SArr[X]);
                }

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

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

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