結果

問題 No.3291 K-step Navigation
ユーザー tobisatis
提出日時 2025-09-17 21:49:48
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 215 ms / 3,000 ms
コード長 1,597 bytes
コンパイル時間 8,334 ms
コンパイル使用メモリ 171,144 KB
実行使用メモリ 189,848 KB
最終ジャッジ日時 2025-10-03 23:29:35
合計ジャッジ時間 14,215 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 51
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (114 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff # 

#nullable enable

int n, m, s, t;
long k;
{
    var input = Console.ReadLine()!.Split(' ');
    n = int.Parse(input[0]);
    m = int.Parse(input[1]);
    k = long.Parse(input[2]);
    s = int.Parse(input[3]) - 1;
    t = int.Parse(input[4]) - 1;
}
var adjacencies = new List<int>[n];
for (var i = 0; i < n; i++) adjacencies[i] = new();
for (var i = 0; i < m; i++)
{
    var input = Console.ReadLine()!.Split(' ');
    var u = int.Parse(input[0]) - 1;
    var v = int.Parse(input[1]) - 1;
    adjacencies[u].Add(v);
    adjacencies[v].Add(u);
}

bool Solve()
{
    if (k % 2 != 0) return true;
    if (adjacencies[s].Exists(v => v != t)) return true;
    if (adjacencies[t].Exists(v => v != s)) return true;
    if (!adjacencies[s].Contains(t)) return false;
    var max = int.MaxValue / 2;
    for (var o = 0; o < n; o++)
    {
        var closest = new int[n];
        closest.AsSpan().Fill(max);
        closest[o] = 0;
        var q = new Queue<int>();
        q.Enqueue(o);
        while (q.Count > 0)
        {
            var v = q.Dequeue();
            var nv = closest[v] + 1;
            foreach (var next in adjacencies[v])
            {
                var cv = closest[next];
                if (cv < max)
                {
                    var ret = nv + cv;
                    if (ret % 2 != 0 && ret + 3 <= k) return true;
                }
                if (nv < cv)
                {
                    closest[next] = nv;
                    q.Enqueue(next);
                }
            }
        }
    }
    return false;
}

Console.WriteLine(Solve() ? "Yes" : "No");
0