結果
| 問題 | No.3291 K-step Navigation | 
| コンテスト | |
| ユーザー |  | 
| 提出日時 | 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/
ソースコード
#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");
            
            
            
        