結果
問題 |
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.
ソースコード
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; } }