結果

問題 No.17 2つの地点に泊まりたい
ユーザー 44
提出日時 2015-10-23 12:29:04
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 7,540 bytes
コンパイル時間 995 ms
コンパイル使用メモリ 111,104 KB
実行使用メモリ 23,808 KB
最終ジャッジ日時 2024-07-22 23:03:07
合計ジャッジ時間 3,674 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
19,328 KB
testcase_01 AC 39 ms
19,456 KB
testcase_02 AC 40 ms
19,456 KB
testcase_03 AC 40 ms
20,736 KB
testcase_04 WA -
testcase_05 AC 83 ms
23,424 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 142 ms
23,552 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 36 ms
19,328 KB
testcase_13 AC 36 ms
19,200 KB
testcase_14 AC 37 ms
19,072 KB
testcase_15 AC 36 ms
19,328 KB
testcase_16 AC 37 ms
19,584 KB
testcase_17 AC 37 ms
19,328 KB
testcase_18 AC 44 ms
22,400 KB
testcase_19 AC 38 ms
19,200 KB
testcase_20 AC 38 ms
19,456 KB
testcase_21 AC 37 ms
19,200 KB
testcase_22 AC 40 ms
21,376 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 + SyukuhakuCost) continue;

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