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