結果

問題 No.160 最短経路のうち辞書順最小
コンテスト
ユーザー 明智重蔵
提出日時 2015-09-19 19:41:06
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 6,243 bytes
コンパイル時間 1,044 ms
コンパイル使用メモリ 110,464 KB
実行使用メモリ 32,512 KB
最終ジャッジ日時 2024-07-19 08:13:18
合計ジャッジ時間 9,355 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other WA * 3 TLE * 1 -- * 22
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
using System.Text.RegularExpressions;

class Program
{
    static string InputPattern = "Input5";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("4 3 0 3");
            WillReturn.Add("0 2 100");
            WillReturn.Add("2 1 200");
            WillReturn.Add("1 3 300");
            //0 2 1 3
            //駅0から駅3に向かう経路は(0,2,1,3)の1つしかないので、これを出力します
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 4 0 3");
            WillReturn.Add("0 2 100");
            WillReturn.Add("2 3 100");
            WillReturn.Add("0 1 200");
            WillReturn.Add("1 3 200");
            //0 2 3
            //駅0から駅3に向かう経路は(0,2,3)と(0,1,3)の2つです。
            //(0,2,3)は移動時間の和が200、(0,1,3)は移動時間の和が400となるので、経路(0,2,3)を出力します。
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4 4 0 3");
            WillReturn.Add("0 2 100");
            WillReturn.Add("2 3 100");
            WillReturn.Add("0 1 100");
            WillReturn.Add("1 3 100");
            //0 1 3
            //サンプル2と同様、駅0から駅3に向かう経路は(0,2,3)と(0,1,3)の2つです。
            //今度は2つの経路の移動時間は等しいですが、
            //(0,2,3)より(0,1,3)の方が辞書順で小さいので、経路(0,1,3)を出力します。 
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("8 28 4 6");
            WillReturn.Add("1 4 15");
            WillReturn.Add("4 5 2457");
            WillReturn.Add("1 6 8234");
            WillReturn.Add("0 7 109");
            WillReturn.Add("5 2 6669");
            WillReturn.Add("0 5 31");
            WillReturn.Add("2 6 1");
            WillReturn.Add("0 3 2896");
            WillReturn.Add("0 4 1493");
            WillReturn.Add("7 5 78");
            WillReturn.Add("5 6 96");
            WillReturn.Add("2 7 7486");
            WillReturn.Add("0 2 66");
            WillReturn.Add("7 6 4776");
            WillReturn.Add("4 2 3820");
            WillReturn.Add("2 3 8843");
            WillReturn.Add("4 7 8276");
            WillReturn.Add("3 1 67");
            WillReturn.Add("1 5 4053");
            WillReturn.Add("1 0 912");
            WillReturn.Add("3 4 82");
            WillReturn.Add("6 3 3165");
            WillReturn.Add("5 3 81");
            WillReturn.Add("1 2 2948");
            WillReturn.Add("4 6 3164");
            WillReturn.Add("3 7 3");
            WillReturn.Add("1 7 70");
            WillReturn.Add("0 6 65");
            //4 1 3 5 0 6
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct RosenInfoDef
    {
        internal int a;
        internal int b;
        internal int c;
    }

    struct JyoutaiDef
    {
        internal int CurrPos;
        internal int SumC;
        internal string Path;
    }

    struct MemoInfoDef
    {
        internal int SumC;
        internal string Path;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray();

        SplitAct(InputList[0]);
        int S = wkArr[2];
        int G = wkArr[3];

        var RosenInfoList = new List<RosenInfoDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            RosenInfoList.Add(
                new RosenInfoDef() { a = wkArr[0], b = wkArr[1], c = wkArr[2] });
        }
        RosenInfoDef[] RosenInfoArr = RosenInfoList.ToArray();
        Array.Sort(RosenInfoArr, (X, Y) => Math.Min(X.a, X.b).CompareTo(Math.Min(Y.a, Y.b)));
        int UB = RosenInfoArr.GetUpperBound(0);

        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrPos = S;
        WillPush.SumC = 0;
        WillPush.Path = S.ToString().PadLeft(3);
        stk.Push(WillPush);

        var MemoDict = new Dictionary<int, MemoInfoDef>();

        string AnswerPath = "";
        int AnswerSumC = int.MaxValue;

        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            //クリア処理
            if (Popped.CurrPos == G) {
                AnswerPath = Popped.Path;
                AnswerSumC = Popped.SumC;
                //Console.WriteLine("解候補{0}を発見。コスト={1}", AnswerPath, AnswerSumC);
                continue;
            }

            for (int I = 0; I <= UB; I++) {
                if (Popped.CurrPos < RosenInfoArr[I].a && Popped.CurrPos < RosenInfoArr[I].b) break;

                if (Popped.CurrPos == RosenInfoArr[I].a) {
                    WillPush.CurrPos = RosenInfoArr[I].b;
                }
                else if (Popped.CurrPos == RosenInfoArr[I].b) {
                    WillPush.CurrPos = RosenInfoArr[I].a;
                }
                else continue;

                WillPush.SumC = Popped.SumC + RosenInfoArr[I].c;
                WillPush.Path = Popped.Path + WillPush.CurrPos.ToString().PadLeft(3);

                if (WillPush.SumC > AnswerSumC) continue;

                if (MemoDict.ContainsKey(WillPush.CurrPos)) {
                    if (MemoDict[WillPush.CurrPos].SumC < WillPush.SumC)
                        continue;
                    if (MemoDict[WillPush.CurrPos].SumC == WillPush.SumC
                     && MemoDict[WillPush.CurrPos].Path.CompareTo(WillPush.Path) <= 0)
                        continue;
                }
                MemoDict[WillPush.CurrPos] =
                    new MemoInfoDef() { SumC = WillPush.SumC, Path = WillPush.Path };

                stk.Push(WillPush);
            }
        }
        AnswerPath = Regex.Replace(AnswerPath, "^ +", "");
        AnswerPath = Regex.Replace(AnswerPath, " +", " ");
        Console.WriteLine(AnswerPath);
    }
}
0