結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 15:18:18 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 103 ms / 2,000 ms |
コード長 | 1,430 bytes |
コンパイル時間 | 3,754 ms |
コンパイル使用メモリ | 289,976 KB |
実行使用メモリ | 17,012 KB |
最終ジャッジ日時 | 2025-09-06 15:18:29 |
合計ジャッジ時間 | 6,423 ms |
ジャッジサーバーID (参考情報) |
judge / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, s, n) for(int i=(0+s); i < (n+s); i++) //pair<T, T>-> P<T> template<class T> using P = pair<T, T>; template<class T> struct item {T A, B, C;}; ll N, M, K; vector<vector<ll>>G; const ll INF = 1'000'000'000'000'000; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin>> N >> M; G.resize(N); for(int i=0; i<M; i++){ ll u, v; cin >> u >> v; u--, v--; G[u].push_back(v); G[v].push_back(u); } cin>> K; vector<bool> iwai(100009); rep(i, 0, K) { ll a; cin >> a; a--; iwai[a]=true; } queue<pair<ll, ll>> Q; Q.push(make_pair(0, 0)); vector<vector<ll>> dist(N, vector<ll>(5, -1)); dist[0][0]=0; while(!Q.empty()) { auto [pos, cnt] = Q.front(); Q.pop(); for(ll npos : G[pos]) { ll ncnt=cnt; if(cnt==5 && iwai[npos])continue; if(iwai[npos]){ ncnt++; }else ncnt=0; if(dist[npos][ncnt]!=-1)continue; Q.push({npos, ncnt}); dist[npos][ncnt]=dist[pos][cnt]+1; } } ll ans=INF; for(int i=0; i<5; i++){ if(dist[N-1][i]==-1)continue; ans = min(ans, dist[N-1][i]); } if(ans==INF)cout << -1 << endl; else cout << ans << endl; return 0; }