結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
![]() |
提出日時 | 2025-09-06 14:17:51 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 398 ms / 2,000 ms |
コード長 | 4,988 bytes |
コンパイル時間 | 9,069 ms |
コンパイル使用メモリ | 168,412 KB |
実行使用メモリ | 227,840 KB |
最終ジャッジ日時 | 2025-09-06 14:18:16 |
合計ジャッジ時間 | 17,012 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (102 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System; using System.Collections.Generic; using System.Linq; class Program { static string InputPattern = "InputX"; static List<string> GetInputList() { var WillReturn = new List<string>(); if (InputPattern == "Input1") { WillReturn.Add("13 13"); WillReturn.Add("1 2"); WillReturn.Add("2 3"); WillReturn.Add("3 4"); WillReturn.Add("4 5"); WillReturn.Add("5 6"); WillReturn.Add("6 13"); WillReturn.Add("1 7"); WillReturn.Add("7 8"); WillReturn.Add("8 9"); WillReturn.Add("9 10"); WillReturn.Add("9 12"); WillReturn.Add("10 11"); WillReturn.Add("11 13"); WillReturn.Add("10"); WillReturn.Add("2 3 4 5 6 7 8 9 10 11"); //8 } else if (InputPattern == "Input2") { WillReturn.Add("7 6"); WillReturn.Add("1 2"); WillReturn.Add("2 3"); WillReturn.Add("3 4"); WillReturn.Add("4 5"); WillReturn.Add("5 6"); WillReturn.Add("6 7"); WillReturn.Add("5"); WillReturn.Add("2 3 4 5 6"); //-1 } else if (InputPattern == "Input3") { WillReturn.Add("3 2"); WillReturn.Add("1 2"); WillReturn.Add("2 3"); WillReturn.Add("0"); //2 } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } static long[] GetSplitArr(string pStr) { return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray(); } static HashSet<long> mKSet = new HashSet<long>(); // 隣接リスト static Dictionary<long, List<long>> mToNodeListDict = new Dictionary<long, List<long>>(); static long mN; static void Main() { List<string> InputList = GetInputList(); long[] wkArr = { }; Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr); SplitAct(InputList[0]); mN=wkArr[0]; long M = wkArr[1]; foreach (string EachStr in InputList.Skip(1).Take((int)M)) { SplitAct(EachStr); long FromNode = wkArr[0]; long ToNode = wkArr[1]; if (mToNodeListDict.ContainsKey(FromNode) == false) { mToNodeListDict[FromNode] = new List<long>(); } if (mToNodeListDict.ContainsKey(ToNode) == false) { mToNodeListDict[ToNode] = new List<long>(); } mToNodeListDict[FromNode].Add(ToNode); mToNodeListDict[ToNode].Add(FromNode); } long K = long.Parse(InputList[(int)M + 1]); if (K >= 1) { SplitAct(InputList.Last()); mKSet.UnionWith(wkArr); } var Que = new Queue<JyoutaiDef>(); JyoutaiDef WillEnqueue; WillEnqueue.CurrNode = 1; WillEnqueue.IwaiCnt = 0; WillEnqueue.Cost = 0; Que.Enqueue(WillEnqueue); long Answer = long.MaxValue; bool HasAnswer = false; // 最小コスト[ハッシュ] var EadakiriDict = new Dictionary<long, long>(); while (Que.Count > 0) { JyoutaiDef Dequeued=Que.Dequeue(); // クリア判定 if (Dequeued.CurrNode == mN) { HasAnswer = true; Answer = Math.Min(Answer, Dequeued.Cost); continue; } if (HasAnswer) { if (Answer <= Dequeued.Cost) continue; } foreach (long EachToNode in mToNodeListDict[Dequeued.CurrNode]) { WillEnqueue.CurrNode = EachToNode; WillEnqueue.IwaiCnt = Dequeued.IwaiCnt; if (mKSet.Contains(EachToNode)) { WillEnqueue.IwaiCnt++; } else { WillEnqueue.IwaiCnt = 0; } if (WillEnqueue.IwaiCnt == 5) continue; WillEnqueue.Cost = Dequeued.Cost + 1; long Hash = GetHash(EachToNode, WillEnqueue.IwaiCnt); if (EadakiriDict.ContainsKey(Hash)) { if (EadakiriDict[Hash] <= WillEnqueue.Cost) { continue; } } EadakiriDict[Hash] = WillEnqueue.Cost; Que.Enqueue(WillEnqueue); } } if (HasAnswer) { Console.WriteLine(Answer); } else { Console.WriteLine(-1); } } static long GetHash(long pNode, long pIwaiCnt) { return pNode * 10 + pIwaiCnt; } struct JyoutaiDef { internal long CurrNode; internal long IwaiCnt; internal long Cost; } }