結果
問題 |
No.2565 はじめてのおつかい
|
ユーザー |
![]() |
提出日時 | 2025-02-18 17:32:32 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 280 ms / 2,000 ms |
コード長 | 4,381 bytes |
コンパイル時間 | 2,686 ms |
コンパイル使用メモリ | 110,464 KB |
実行使用メモリ | 56,096 KB |
最終ジャッジ日時 | 2025-02-18 17:32:48 |
合計ジャッジ時間 | 13,358 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 50 |
コンパイルメッセージ
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; // https://yukicoder.me/problems/no/2565 class Program { static string InputPattern = "InputX"; static List<string> GetInputList() { var WillReturn = new List<string>(); if (InputPattern == "Input1") { WillReturn.Add("4 6"); WillReturn.Add("1 2"); WillReturn.Add("2 4"); WillReturn.Add("2 3"); WillReturn.Add("3 1"); WillReturn.Add("3 4"); WillReturn.Add("4 3"); //4 } else if (InputPattern == "Input2") { WillReturn.Add("3 3"); WillReturn.Add("1 2"); WillReturn.Add("3 1"); WillReturn.Add("2 1"); //-1 } else if (InputPattern == "Input3") { WillReturn.Add("7 12"); WillReturn.Add("1 2"); WillReturn.Add("1 4"); WillReturn.Add("1 5"); WillReturn.Add("2 5"); WillReturn.Add("3 1"); WillReturn.Add("3 2"); WillReturn.Add("4 1"); WillReturn.Add("4 6"); WillReturn.Add("5 1"); WillReturn.Add("5 6"); WillReturn.Add("6 7"); WillReturn.Add("7 3"); //5 } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } static int mN; // 隣接リスト static Dictionary<int, List<int>> mToNodeListDict = new Dictionary<int, List<int>>(); static void Main() { List<string> InputList = GetInputList(); int[] wkArr = { }; Action<string> SplitAct = pStr => wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray(); SplitAct(InputList[0]); mN = wkArr[0]; foreach (string EachStr in InputList.Skip(1)) { SplitAct(EachStr); int FromNode = wkArr[0]; int ToNode = wkArr[1]; if (mToNodeListDict.ContainsKey(FromNode) == false) { mToNodeListDict[FromNode] = new List<int>(); } mToNodeListDict[FromNode].Add(ToNode); } var AnswerList = new List<int>(); bool Result1, Result2, Result3; int Cost1 = ExecBFS(out Result1, 1, mN - 1); int Cost2 = ExecBFS(out Result2, mN - 1, mN); int Cost3 = ExecBFS(out Result3, mN, 1); if (Result1 && Result2 && Result3) { AnswerList.Add(Cost1 + Cost2 + Cost3); } Cost1 = ExecBFS(out Result1, 1, mN); Cost2 = ExecBFS(out Result2, mN, mN - 1); Cost3 = ExecBFS(out Result3, mN - 1, 1); if (Result1 && Result2 && Result3) { AnswerList.Add(Cost1 + Cost2 + Cost3); } if (AnswerList.Count > 0) { Console.WriteLine(AnswerList.Min()); } else { Console.WriteLine(-1); } } // 始点と終点を引数として、コストを返す static int ExecBFS(out bool pHasAnswer, int pStaNode, int pGoalNode) { //Console.WriteLine("pStaNode={0},pGoalNode={1}", pStaNode, pGoalNode); pHasAnswer = false; var VisitedSet = new HashSet<int>(); VisitedSet.Add(pStaNode); var Que = new Queue<JyoutaiDef>(); JyoutaiDef WillEnqueue; WillEnqueue.CurrNode = pStaNode; WillEnqueue.Level = 0; Que.Enqueue(WillEnqueue); while (Que.Count > 0) { JyoutaiDef Dequeued = Que.Dequeue(); //Console.WriteLine("CurrNode={0}", Dequeued.CurrNode); if (Dequeued.CurrNode == pGoalNode) { pHasAnswer = true; return Dequeued.Level; } if (mToNodeListDict.ContainsKey(Dequeued.CurrNode)) { foreach (int EachToNode in mToNodeListDict[Dequeued.CurrNode]) { if (VisitedSet.Add(EachToNode)) { WillEnqueue.CurrNode = EachToNode; WillEnqueue.Level = Dequeued.Level + 1; Que.Enqueue(WillEnqueue); } } } } return int.MaxValue; } struct JyoutaiDef { internal int CurrNode; internal int Level; } }