結果

問題 No.17 2つの地点に泊まりたい
コンテスト
ユーザー 明智重蔵
提出日時 2015-10-20 21:09:04
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 7,114 bytes
コンパイル時間 2,293 ms
コンパイル使用メモリ 119,120 KB
実行使用メモリ 31,884 KB
最終ジャッジ日時 2024-07-22 11:06:22
合計ジャッジ時間 4,086 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 14 WA * 13
権限があれば一括ダウンロードができます
コンパイルメッセージ
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> SyokuhakuIndList;
        //internal string Path;
    }

    //17 2つの地点に泊まりたい
    //http://yukicoder.me/problems/61
    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.SyokuhakuIndList = new List<int>();
        //WillPush.Path = "0,";
        stk.Push(WillPush);

        //最小コスト[移動先ノード][宿の数]なメモ
        Nullable<int>[,] MemoArr = new Nullable<int>[N, 2 + 1];

        int Answer = int.MaxValue;

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

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

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

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

                    int NewSyokuhakuCost = SArr[LoopY];

                    if (Popped.SyokuhakuIndList.Count <= 1
                     || NewSyokuhakuCost < Popped.SyokuhakuIndList.Min(X => SArr[X])) {
                        WillPush.SyokuhakuIndList = new List<int>(Popped.SyokuhakuIndList);
                        WillPush.SyokuhakuIndList.Add(LoopY);
                        WillPush.SyokuhakuIndList =
                           WillPush.SyokuhakuIndList.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 SumCost = WillPush.MoveCost + WillPush.SyokuhakuIndList.Sum(X => SArr[X]);
                int SyokuhakuCount = WillPush.SyokuhakuIndList.Count;
                if (MemoArr[WillPush.CurrPos, SyokuhakuCount] != null) {
                    if (MemoArr[WillPush.CurrPos, SyokuhakuCount].Value <= SumCost)
                        continue;
                }
                MemoArr[WillPush.CurrPos, SyokuhakuCount] = SumCost;

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

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