結果
問題 | No.92 逃走経路 |
ユーザー |
![]() |
提出日時 | 2024-10-10 22:41:09 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 921 ms / 5,000 ms |
コード長 | 3,320 bytes |
コンパイル時間 | 1,213 ms |
コンパイル使用メモリ | 109,440 KB |
実行使用メモリ | 20,608 KB |
最終ジャッジ日時 | 2024-10-10 22:41:18 |
合計ジャッジ時間 | 8,481 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 |
コンパイルメッセージ
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;class Program{static string InputPattern = "InputX";static List<string> GetInputList(){var WillReturn = new List<string>();if (InputPattern == "Input1") {WillReturn.Add("3 2 2");WillReturn.Add("1 2 10");WillReturn.Add("2 3 20");WillReturn.Add("10 20");//1//3//犯人は通行料金10の道路を通り、続いて通行料金20の道路を通った。//ここから犯人は今町3にいると分かる。}else if (InputPattern == "Input2") {WillReturn.Add("3 2 2");WillReturn.Add("1 2 10");WillReturn.Add("1 2 20");WillReturn.Add("10 20");//2//1 2//ある町のペアを複数本の道路が結ぶこともある。//また、どの町のペアも互いに行き来できるとは限らない。}else {string wkStr;while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);}return WillReturn;}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 M = wkArr[1];//隣接行列のListでグラフを定義var RinsetuGyouretuListArr = new List<int>[N + 1, N + 1];foreach (string EachStr in InputList.Skip(1).Take(M)) {SplitAct(EachStr);if (RinsetuGyouretuListArr[wkArr[0], wkArr[1]] == null)RinsetuGyouretuListArr[wkArr[0], wkArr[1]] = new List<int>();if (RinsetuGyouretuListArr[wkArr[1], wkArr[0]] == null)RinsetuGyouretuListArr[wkArr[1], wkArr[0]] = new List<int>();RinsetuGyouretuListArr[wkArr[0], wkArr[1]].Add(wkArr[2]);RinsetuGyouretuListArr[wkArr[1], wkArr[0]].Add(wkArr[2]);}string wkStr = InputList.ElementAt(1 + M);int[] DArr = wkStr.Split(' ').Select(X => int.Parse(X)).ToArray();//到達可否[町番号]なDP表bool[] PrevDP = new bool[N + 1];for (int I = 1; I <= PrevDP.GetUpperBound(0); I++)PrevDP[I] = true;foreach (int EachInt in DArr) {bool[] CurrDP = new bool[N + 1];for (int I = 1; I <= PrevDP.GetUpperBound(0); I++) {if (PrevDP[I] == false) continue;for (int J = 1; J <= RinsetuGyouretuListArr.GetUpperBound(1); J++) {if (RinsetuGyouretuListArr[I, J] == null) continue;if (RinsetuGyouretuListArr[I, J].Contains(EachInt)) {CurrDP[J] = true;}}}PrevDP = CurrDP;}Console.WriteLine(PrevDP.Count(X => X));var sb = new System.Text.StringBuilder();for (int I = 1; I <= PrevDP.GetUpperBound(0); I++) {if (PrevDP[I]) sb.AppendFormat("{0} ", I);}Console.WriteLine(sb.ToString().TrimEnd());}}