結果
問題 | No.160 最短経路のうち辞書順最小 |
ユーザー | 明智重蔵 |
提出日時 | 2015-09-27 19:03:17 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 6,199 bytes |
コンパイル時間 | 3,628 ms |
コンパイル使用メモリ | 109,096 KB |
実行使用メモリ | 37,188 KB |
最終ジャッジ日時 | 2023-09-26 16:56:29 |
合計ジャッジ時間 | 29,471 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 136 ms
26,356 KB |
testcase_01 | AC | 137 ms
26,336 KB |
testcase_02 | AC | 138 ms
26,140 KB |
testcase_03 | AC | 138 ms
26,144 KB |
testcase_04 | AC | 630 ms
31,132 KB |
testcase_05 | AC | 1,089 ms
34,456 KB |
testcase_06 | AC | 1,530 ms
33,820 KB |
testcase_07 | AC | 717 ms
32,280 KB |
testcase_08 | AC | 658 ms
34,868 KB |
testcase_09 | AC | 371 ms
32,348 KB |
testcase_10 | AC | 814 ms
34,728 KB |
testcase_11 | AC | 912 ms
32,868 KB |
testcase_12 | AC | 723 ms
34,824 KB |
testcase_13 | AC | 574 ms
34,576 KB |
testcase_14 | AC | 900 ms
35,208 KB |
testcase_15 | AC | 740 ms
35,032 KB |
testcase_16 | AC | 436 ms
34,924 KB |
testcase_17 | AC | 778 ms
32,548 KB |
testcase_18 | AC | 586 ms
33,640 KB |
testcase_19 | AC | 403 ms
32,460 KB |
testcase_20 | AC | 424 ms
32,548 KB |
testcase_21 | AC | 746 ms
34,108 KB |
testcase_22 | AC | 771 ms
33,732 KB |
testcase_23 | AC | 668 ms
33,624 KB |
testcase_24 | AC | 524 ms
31,044 KB |
testcase_25 | AC | 618 ms
34,232 KB |
testcase_26 | AC | 608 ms
37,188 KB |
testcase_27 | AC | 274 ms
31,388 KB |
testcase_28 | TLE | - |
testcase_29 | -- | - |
コンパイルメッセージ
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; } 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); } }