結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
![]() |
提出日時 | 2025-09-06 13:57:13 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 150 ms / 2,000 ms |
コード長 | 1,250 bytes |
コンパイル時間 | 8,473 ms |
コンパイル使用メモリ | 219,972 KB |
実行使用メモリ | 14,880 KB |
最終ジャッジ日時 | 2025-09-06 13:58:12 |
合計ジャッジ時間 | 11,906 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int N, M; cin >> N >> M; int U, V; vector<vector<int>> g(N); for (int i = 0; i < M; ++i) { cin >> U >> V; U--, V--; g[U].push_back(V); g[V].push_back(U); } int K; cin >> K; int A; vector<bool> Y(N, false); for (int i = 0; i < K; ++i) { cin >> A; A--; Y[A] = true; } vector<vector<int>> len(N, vector<int>(5, -1)); len[0][0] = 0; queue<pair<int, int>> que; que.emplace(0, 0); while (que.size()) { int tmp = que.front().first, cnt = que.front().second; que.pop(); for (auto x : g[tmp]) { if (Y[x]) { if (cnt == 4) continue; if (len[x][cnt + 1] != -1) continue; len[x][cnt + 1] = len[tmp][cnt] + 1; que.emplace(x, cnt + 1); } else { if (len[x][0] != -1) continue; len[x][0] = len[tmp][cnt] + 1; que.emplace(x, 0); } } } cout << len[N - 1][0] << endl; return 0; }