結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
![]() |
提出日時 | 2025-09-06 14:04:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 127 ms / 2,000 ms |
コード長 | 2,465 bytes |
コンパイル時間 | 4,511 ms |
コンパイル使用メモリ | 260,036 KB |
実行使用メモリ | 17,052 KB |
最終ジャッジ日時 | 2025-09-06 14:04:59 |
合計ジャッジ時間 | 7,375 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll=long long; using ld=long double; #define rep(i,n) for(ll i=0;i<n;i++) #define repd(i,n) for(ll i=n-1;i>=0;i--) #define rep1(i,n) for(ll i=1;i<=n;i++) #define rep_lt(i,j,k) for(ll i=j;i<k;i++) //[j,k) void printd(ld x){cout<<fixed<<setprecision(16)<<x<<endl;} void printd2(ld x,ld y){ cout<<fixed<<setprecision(16)<<x<<' '<<y<<endl; } template<typename Vec> void vcout(const Vec& vec){ for(auto& v:vec) cout<<v<<' '; cout<<'\n'; } template<typename Vec> void vcout_val(const Vec& vec){ for(auto& v:vec) cout<<v.val()<<' '; cout<<'\n'; } template<typename Vec> void vvcout(const Vec& vec){ for(auto& v:vec){ for(auto& k:v) cout<<k; cout<<'\n'; } } template<typename Vec> void vvcout_s(const Vec& vec){ for(auto& v:vec){ for(auto& k:v) cout<<k<<' '; cout<<'\n'; } } template<typename Vec> void vvcout_val(const Vec& vec){ for(auto& v:vec){ for(auto& k:v) cout<<k.val()<<' '; cout<<'\n'; } } template<typename T,typename U> void chmax(T& a,const U& b){ if(a<b) a=b; } template<typename T,typename U> void chmin(T& a,const U& b) { if(a>b) a=b; } struct FastIO{ FastIO(){ ios::sync_with_stdio(false); cin.tie(nullptr); } }fastio; void YN(bool state){cout<<(state?"Yes\n":"No\n");} void CY(bool state){if(state)cout<<"Yes"<<endl,exit(0);} void CN(bool state){if(state)cout<<"No"<<endl,exit(0);} void Cm1(bool state){if(state)cout<<-1<<endl,exit(0);} const ll INF=4e18; #define all(p) p.begin(),p.end() #define rall(p) p.rbegin(),p.rend() #include <atcoder/all> using namespace atcoder; using mint=modint998244353; //using mint=modint1000000007; using T=tuple<ll,ll,ll>; using P=pair<ll,ll>; //考察 int main(){ ll n,m; cin>>n>>m; vector<vector<ll>> to(n); rep(i,m){ ll a,b; cin>>a>>b; a--;b--; to[a].push_back(b); to[b].push_back(a); } ll k;cin>>k; vector<bool> iwai(n); rep(i,k){ ll a;cin>>a; a--; iwai[a]=true; } queue<P> q; vector<vector<ll>> dist(n,vector<ll>(5,INF)); auto push=[&](ll v,ll cnt,ll d)->void{ if(iwai[v]) cnt++;else cnt=0; if(cnt==5) return; if(dist[v][cnt]!=INF) return; dist[v][cnt]=d; q.emplace(v,cnt); }; push(0,0,0); while(q.size()){ auto [now,cnt]=q.front();q.pop(); ll d=dist[now][cnt]; for(auto next:to[now]) push(next,cnt,d+1); } ll ans=*min_element(all(dist[n-1])); if(ans==INF) ans=-1; cout<<ans<<endl; return 0; }