結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 13:39:32 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 149 ms / 2,000 ms |
コード長 | 1,208 bytes |
コンパイル時間 | 1,080 ms |
コンパイル使用メモリ | 106,504 KB |
実行使用メモリ | 15,488 KB |
最終ジャッジ日時 | 2025-09-06 13:40:09 |
合計ジャッジ時間 | 4,944 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <iostream> #include <vector> #include <array> #include <queue> int main() { int N, M; std::cin >> N >> M; std::vector<std::vector<int>> graph(N); while (M--) { int U, V; std::cin >> U >> V; U--, V--; graph[U].emplace_back(V); graph[V].emplace_back(U); } std::vector<bool> has_yiwiy9(N); int K; std::cin >> K; while (K--) { int A; std::cin >> A; A--; has_yiwiy9[A] = true; } std::vector<std::vector<int>> dist(N, std::vector<int>(5, -1)); std::queue<std::array<int, 3>> queue; queue.push({0, 0, 0}); while (queue.size()) { auto [u, d, n] = queue.front(); queue.pop(); if (dist[u][d] != -1) continue; dist[u][d] = n; for (int v : graph[u]) { int nd = has_yiwiy9[v] ? d + 1 : 0; if (nd == 5) continue; if (dist[v][nd] != -1) continue; queue.push({v, nd, n + 1}); } } int result = -1; for (int d = 0; d < 5; d++) { if (result == -1 || dist[N - 1][d] != -1 && result > dist[N - 1][d]) result = dist[N - 1][d]; } std::cout << result << std::endl; }