結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
![]() |
提出日時 | 2025-08-18 13:59:39 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 119 ms / 2,000 ms |
コード長 | 1,586 bytes |
コンパイル時間 | 4,963 ms |
コンパイル使用メモリ | 335,508 KB |
実行使用メモリ | 13,376 KB |
最終ジャッジ日時 | 2025-08-18 13:59:49 |
合計ジャッジ時間 | 9,807 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#if __has_include(<yoniha/all.h>) #include <yoniha/all.h> using namespace atcoder; #else #include <bits/stdc++.h> #if __has_include(<atcoder/all>) #include <atcoder/all> using namespace atcoder; #endif #endif using namespace std; #define int long long #define all(x) (x).begin(), (x).end() #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rrep(i, n) for(int i = (int)((n) - 1); i >= 0; i--) template <typename T> bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template <typename T> bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;} // using mint = modint; signed main(){ int n, m; cin >> n >> m; vector g(n, vector<int>(0)); while(m--){ int u, v; cin >> u >> v; u--; v--; g.at(u).emplace_back(v); g.at(v).emplace_back(u); } int k; cin >> k; vector<bool> iwai(n, false); while(k--){ int a; cin >> a; a--; iwai.at(a) = true; } vector<int> seen(5 * n, -1); seen.at(0) = 0; deque<int> bfs; bfs.emplace_back(0); while(!bfs.empty()){ int from = bfs.front(); bfs.pop_front(); for(auto t : g.at(from % n)){ int to = t + (iwai.at(t) ? from / n * n + n : 0); if(to >= 5 * n || seen.at(to) != -1) continue; seen.at(to) = seen.at(from) + 1; bfs.emplace_back(to); } } int ans = 1ll << 60; rep(i, 5) if(seen.at(n - 1 + i * n) != -1) chmin(ans, seen.at(n - 1 + i * n)); // rep(i, 5) cout << seen.at(n - 1 + i * n) << '\n'; cout << (ans == 1ll << 60 ? -1 : ans) << '\n'; } /* 頂点を5倍にする? streakを途切れさせる処理を入れていない */