結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
![]() |
提出日時 | 2025-09-06 17:31:26 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 468 ms / 2,000 ms |
コード長 | 4,590 bytes |
コンパイル時間 | 7,919 ms |
コンパイル使用メモリ | 168,984 KB |
実行使用メモリ | 219,508 KB |
最終ジャッジ日時 | 2025-09-06 17:31:49 |
合計ジャッジ時間 | 17,253 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (97 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using HatoLibrary; using System.Diagnostics; class Program { static string ReadLine() => Console.ReadLine().Trim(); static int ReadInt() => int.Parse(ReadLine()); static long ReadLong() => long.Parse(ReadLine()); static int[] ReadIntArray() { string str = ReadLine(); return str != "" ? str.Split().Select(_ => int.Parse(_)).ToArray() : new int[0]; } static long[] ReadLongArray() { string str = ReadLine(); return str != "" ? str.Split().Select(_ => long.Parse(_)).ToArray() : new long[0]; } static (int a, int b) ReadInt2() { int[] vs = ReadIntArray(); return (a: vs[0], b: vs[1]); } static (int a, int b, int c) ReadInt3() { int[] vs = ReadIntArray(); return (a: vs[0], b: vs[1], c: vs[2]); } static (int a, int b, int c, int d) ReadInt4() { int[] vs = ReadIntArray(); return (a: vs[0], b: vs[1], c: vs[2], d: vs[3]); } static (long a, long b) ReadLong2() { long[] vs = ReadLongArray(); return (a: vs[0], b: vs[1]); } static (long a, long b, long c) ReadLong3() { long[] vs = ReadLongArray(); return (a: vs[0], b: vs[1], c: vs[2]); } static (long a, long b, long c, long d) ReadLong4() { long[] vs = ReadLongArray(); return (a: vs[0], b: vs[1], c: vs[2], d: vs[3]); } static void Main() { SourceExpander.Expander.Expand(); (int N, int M) = ReadInt2(); int[] U = new int[M]; int[] V = new int[M]; for (int i = 0; i < M; i++) { (int u, int v) = ReadInt2(); U[i] = u - 1; V[i] = v - 1; } int K = ReadInt(); HashSet<int> A = new HashSet<int>(); if(K > 0) A = new HashSet<int>(ReadIntArray().Select(_ => _ - 1)); Bfs bfs = new Bfs(N * 5); for (int i = 0; i < M; i++) { AddEdges(U[i], V[i]); AddEdges(V[i], U[i]); } long[] rets = bfs.Solve(0); long ans = long.MaxValue; for (int i = 0; i < 5; i++) ans = Math.Min(ans, rets[N - 1 + N * i]); if(ans < long.MaxValue) Console.WriteLine(ans); else Console.WriteLine(-1); void AddEdges(int a, int b) { if (A.Contains(b)) { for (int i = 0; i < 5 - 1; i++) bfs.AddEdge(a + N * i, b + N * (i + 1)); } else { for (int i = 0; i < 5; i++) bfs.AddEdge(a + N * i, b); } } } } #region Expanded by https://github.com/kzrnm/SourceExpander namespace HatoLibrary { public class Bfs { int N = 0; List<int>[] Nexts; public Bfs(int n) { N = n; Nexts = new List<int>[N]; ; for (int i = 0; i < N; i++) Nexts[i] = new List<int>(); } public void AddEdge(int from, int next) { Nexts[from].Add(next); } public long[] Solve(int start) { long[] costs = new long[N]; for (int i = 0; i < N; i++) costs[i] = long.MaxValue; Queue<int> q = new Queue<int>(); q.Enqueue(start); costs[start] = 0; while (q.Count > 0) { int cur = q.Dequeue(); foreach (int next in Nexts[cur]) { long ncost = costs[cur] + 1; if (costs[next] > ncost) { costs[next] = ncost; q.Enqueue(next); } } } return costs; } public List<int> Solve(int start, int goal) { List<int> path = new List<int>(); long[] costs = new long[N]; for (int i = 0; i < N; i++) costs[i] = long.MaxValue; int[] froms = new int[N]; Queue<int> q = new Queue<int>(); q.Enqueue(start); costs[start] = 0; froms[start] = -1; while (q.Count > 0) { int cur = q.Dequeue(); foreach (int next in Nexts[cur]) { long ncost = costs[cur] + 1; if (costs[next] > ncost) { costs[next] = ncost; froms[next] = cur; q.Enqueue(next); } } } if (costs[goal] == long.MaxValue) return path; int last = goal; while (last != -1) { path.Add(last); last = froms[last]; } path.Reverse(); return path; } public long[] Solve(int[] starts) { long[] costs = new long[N]; for (int i = 0; i < N; i++) costs[i] = long.MaxValue; Queue<int> q = new Queue<int>(); foreach (int start in starts) { q.Enqueue(start); costs[start] = 0; } while (q.Count > 0) { int cur = q.Dequeue(); foreach (int next in Nexts[cur]) { long ncost = costs[cur] + 1; if (costs[next] > ncost) { costs[next] = ncost; q.Enqueue(next); } } } return costs; } } } namespace SourceExpander{public class Expander{[Conditional("EXP")]public static void Expand(string inputFilePath=null,string outputFilePath=null,bool ignoreAnyError=true){}public static string ExpandString(string inputFilePath=null,bool ignoreAnyError=true){return "";}}} #endregion Expanded by https://github.com/kzrnm/SourceExpander