結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 14:13:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 205 ms / 2,000 ms |
コード長 | 1,230 bytes |
コンパイル時間 | 2,306 ms |
コンパイル使用メモリ | 211,456 KB |
実行使用メモリ | 18,808 KB |
最終ジャッジ日時 | 2025-09-06 14:13:51 |
合計ジャッジ時間 | 6,394 ms |
ジャッジサーバーID (参考情報) |
judge / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, n) for (int i = 0; i < (ll)(n); i++) #define oke cout << "Yes" << '\n'; #define dame cout << "No" << '\n'; #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() using HaiI = vector<vector<int>>; using Hai2 = vector<vector<ll>>; using HaiB = vector<vector<bool>>; using Hai3 = vector<vector<vector<ll>>>; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); ll N,M; cin>>N>>M; Hai2 G(N); rep(i,M){ int a,b; cin>>a>>b; a--,b--; G[a].push_back(b); G[b].push_back(a); } ll K; cin>>K; set<ll>A; rep(i,K){ int a; cin>>a; a--; A.insert(a); } queue<pair<int,int>>Q; Hai2 dist(N,vector<ll>(5,1e9)); Q.push({0,0}); dist[0][0]=0; while(!Q.empty()){ int h,v; tie(v,h)=Q.front(); Q.pop(); for(int x:G[v]){ if(A.count(x)){ if(h==4) continue; if(dist[x][h+1] > dist[v][h]+1){ dist[x][h+1]=dist[v][h]+1; Q.push({x,h+1}); } }else{ if(dist[x][0] > dist[v][h]+1){ dist[x][0]=dist[v][h]+1; Q.push({x,0}); } } } } ll ans=1e9; rep(i,5){ ans=min(ans,dist[N-1][i]); } if(ans==1e9) ans=-1; cout<<ans<<"\n"; }