結果
問題 |
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");