結果

問題 No.160 最短経路のうち辞書順最小
ユーザー 明智重蔵
提出日時 2015-09-27 20:01:40
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 7,126 bytes
コンパイル時間 4,305 ms
コンパイル使用メモリ 108,928 KB
実行使用メモリ 38,272 KB
最終ジャッジ日時 2024-07-19 10:59:29
合計ジャッジ時間 10,453 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 25 TLE * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 b;
        internal int c;
    }

    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 N = wkArr[0];
        int S = wkArr[2];
        int G = wkArr[3];

        var RosenInfoDict = new Dictionary<int, List<RosenInfoDef>>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            int wkA = wkArr[0], wkB = wkArr[1], wkC = wkArr[2];

            if (RosenInfoDict.ContainsKey(wkA) == false)
                RosenInfoDict.Add(wkA, new List<RosenInfoDef>());
            RosenInfoDict[wkA].Add(new RosenInfoDef() { b = wkB, c = wkC });

            if (RosenInfoDict.ContainsKey(wkB) == false)
                RosenInfoDict.Add(wkB, new List<RosenInfoDef>());
            RosenInfoDict[wkB].Add(new RosenInfoDef() { b = wkA, c = wkC });
        }

        //ダイクストラ法で解く
        var PriorityQueue = new CppPriorityQueue();

        //確定ノードのDict
        var KakuteiNodeDict = new Dictionary<int, NodeMinPathInfoDef>();
        KakuteiNodeDict.Add(S, 
            new NodeMinPathInfoDef() { NodeID = S, MinCost = 0, MinPath = S.ToString().PadLeft(4) });

        //Enqueue処理
        Action<int> EnqueueAct = pFromPos =>
        {
            foreach (RosenInfoDef EachRosenInfo in RosenInfoDict[pFromPos]) {
                //確定ノードならContinue
                if (KakuteiNodeDict.ContainsKey(EachRosenInfo.b)) continue;

                int wkSumKyori = KakuteiNodeDict[pFromPos].MinCost + EachRosenInfo.c;
                string wkPath = KakuteiNodeDict[pFromPos].MinPath + EachRosenInfo.b.ToString().PadLeft(4);

                PriorityQueue.Enqueue(EachRosenInfo.b, wkSumKyori, wkPath);
            }
        };
        EnqueueAct(S);

        while (PriorityQueue.Count > 0) {
            NodeMinPathInfoDef Dequeued = PriorityQueue.Dequeue();
            //確定ノードならContinue
            if (KakuteiNodeDict.ContainsKey(Dequeued.NodeID)) continue;

            KakuteiNodeDict.Add(Dequeued.NodeID, Dequeued);
            
            //Gまでの最短が確定したらBreak
            if (KakuteiNodeDict.ContainsKey(G)) break;

            EnqueueAct(Dequeued.NodeID);
        }

        //foreach (var EachPair in KakuteiNodeDict) {
        //    Console.WriteLine("{0}までの最短距離は{1}、経路は{2}",
        //        EachPair.Key, EachPair.Value.MinCost, EachPair.Value.MinPath);
        //}
        string Answer = KakuteiNodeDict[G].MinPath;
        Answer = Answer.TrimStart();
        Answer = Regex.Replace(Answer, " +", " ");
        Console.WriteLine(Answer);
    }
}

//PriorityQueueもどき
struct NodeMinPathInfoDef
{
    internal int NodeID;
    internal int MinCost;
    internal string MinPath;
}
class CppPriorityQueue
{
    private List<NodeMinPathInfoDef> mItemList = new List<NodeMinPathInfoDef>();

    internal int Count { get { return mItemList.Count; } }

    internal void Enqueue(NodeMinPathInfoDef pNodeMinPathInfo) { mItemList.Add(pNodeMinPathInfo); }

    internal void Enqueue(int pNodeID, int pMinCost, string pMinPath)
    {
        mItemList.Add(new NodeMinPathInfoDef()
        {
            NodeID = pNodeID,
            MinCost = pMinCost,
            MinPath = pMinPath
        });
    }

    internal NodeMinPathInfoDef Dequeue()
    {
        int wkInd = 0;
        for (int I = 1; I <= mItemList.Count - 1; I++) {
            //{距離合計,経路}が最小の要素を返す
            if (mItemList[I].MinCost < mItemList[wkInd].MinCost)
                wkInd = I;
            if (mItemList[I].MinCost == mItemList[wkInd].MinCost
            && mItemList[I].MinPath.CompareTo(mItemList[wkInd].MinPath) < 0)
                wkInd = I;
        }
        NodeMinPathInfoDef WillRetun = mItemList[wkInd];
        mItemList.RemoveAt(wkInd);
        return WillRetun;
    }
}
0