結果

問題 No.160 最短経路のうち辞書順最小
コンテスト
ユーザー 明智重蔵
提出日時 2015-09-27 19:03:17
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 6,199 bytes
コンパイル時間 984 ms
コンパイル使用メモリ 110,720 KB
実行使用メモリ 65,152 KB
最終ジャッジ日時 2024-07-19 10:58:13
合計ジャッジ時間 24,747 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 24 TLE * 1 -- * 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;
    }

    struct NodeMinPathInfoDef
    {
        internal int MinCost;
        internal string MinPath;
    }

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

        //ベルマンフォード法で解く
        //各ノードまでの距離のDict
        var SumKyoriDict = new Dictionary<int, NodeMinPathInfoDef>();
        SumKyoriDict.Add(S, new NodeMinPathInfoDef() { MinCost = 0, MinPath = S.ToString().PadLeft(4) });

        //ノード数-1だけループする
        for (int I = 1; I <= N - 1; I++) {
            bool IsUpdated = false;

            foreach (int EachKey in SumKyoriDict.Keys.ToArray()) {
                //そのノードから訪問可能なノードで
                //最短距離を更新可能なら更新
                foreach (RosenInfoDef EachGraphInfo in RosenInfoDict[EachKey]) {
                    int wkSumKyori = SumKyoriDict[EachKey].MinCost + EachGraphInfo.c;
                    string wkPath = SumKyoriDict[EachKey].MinPath + EachGraphInfo.b.ToString().PadLeft(4);

                    if (SumKyoriDict.ContainsKey(EachGraphInfo.b)) {
                        if (SumKyoriDict[EachGraphInfo.b].MinCost < wkSumKyori)
                            continue;
                        if (SumKyoriDict[EachGraphInfo.b].MinCost == wkSumKyori
                         && SumKyoriDict[EachGraphInfo.b].MinPath.CompareTo(wkPath) < 0)
                            continue;
                    }
                    SumKyoriDict.Remove(EachGraphInfo.b);
                    SumKyoriDict.Add(EachGraphInfo.b,
                        new NodeMinPathInfoDef() { MinCost = wkSumKyori, MinPath = wkPath });
                    IsUpdated = true;
                }
            }
            if (IsUpdated == false) break;
        }
        //foreach (var EachPair in SumKyoriDict) {
        //    Console.WriteLine("{0}までの最短距離は{1}で経路は{2}",
        //        EachPair.Key, EachPair.Value.MinCost, EachPair.Value.MinPath);
        //}
        string Answer = SumKyoriDict[G].MinPath;
        Answer = Answer.TrimStart();
        Answer = Regex.Replace(Answer, " +", " ");
        Console.WriteLine(Answer);
    }
}
0