結果

問題 No.3263 違法な散歩道
コンテスト
ユーザー 鳩でもわかるC#
提出日時 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/

ソースコード

diff # 

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
0