結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 15:05:37 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 196 ms / 2,000 ms |
コード長 | 3,229 bytes |
コンパイル時間 | 4,602 ms |
コンパイル使用メモリ | 295,856 KB |
実行使用メモリ | 19,020 KB |
最終ジャッジ日時 | 2025-09-06 15:05:48 |
合計ジャッジ時間 | 8,794 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
//#pragma GCC optimize("O3") #include<bits/stdc++.h> using namespace std; #define ll long long #define rep(i,n) for (ll i=0;i<(ll)n;i++) #define rrep(i,n) for (ll i=n-1;i>=(ll)0;i--) #define loop(i,m,n) for(ll i=m;i<=(ll)n;i++) #define rloop(i,m,n) for(ll i=m;i>=(ll)n;i--) #define vl vector<ll> #define vvl vector<vector<ll>> #define vdbg(a) rep(ii,a.size()){cout<<a[ii]<<" ";}cout<<endl; #define vpdbg(a) rep(ii,a.size()){cout<<"{"<<a[ii].first<<","<<a[ii].second<<"} ";}cout<<endl; #define vvdbg(a) rep(ii,a.size()){rep(jj,a[ii].size()){cout<<a[ii][jj]<<" ";}cout<<endl;} #define setdbg(a) for(const auto & ii:a){cout<<ii<<" ";}cout<<endl; #define inf 4000000000000000000LL #define mod 998244353LL //#define mod 1000000007LL #define eps 0.000000001 random_device rnd;// 非決定的な乱数生成器 mt19937 mt(rnd());// メルセンヌ・ツイスタの32ビット版、引数は初期シード //#include<boost/multiprecision/cpp_int.hpp> //#define bbi boost::multiprecision::cpp_int //#include<atcoder/lazysegtree> //整数同士の累乗の計算をする。 ll power(ll A, ll B) { ll result = 1; for (ll i=0;i<B;i++){ result *= A; } return result; } // nのk乗をmodで割った余りを計算 ll power_mod(ll n, ll k){ long long result = 1; while (k > 0){ if ((k&1) ==1)result=(result*n)%mod; n=n*n%mod; k >>= 1; } return result; } //受け取った2次元文字の外側に、文字pをコーティングする。 vector<string> pad(vector<string> &s,char p){ ll h=s.size(); ll w=s[0].size(); vector<string> res(h+2,string(w+2,p)); rep(i,h)rep(j,w)res[i+1][j+1]=s[i][j]; return res; } // Union-Find struct UnionFind { vector<int> par, siz; UnionFind(int n) : par(n, -1) , siz(n, 1) { } // 根を求める int root(int x) { if (par[x] == -1) return x; else return par[x] = root(par[x]); } // x と y が同じグループに属するかどうか (根が一致するかどうか) bool issame(int x, int y) { return root(x) == root(y); } // x を含むグループと y を含むグループとを併合する bool unite(int x, int y) { x = root(x), y = root(y); if (x == y) return false; if (siz[x] < siz[y]) swap(x, y); par[y] = x; siz[x] += siz[y]; return true; } // x を含むグループのサイズ int size(int x) { return siz[root(x)]; } }; //グリッド問題等用 vl dx={1,0,-1,0}; vl dy={0,1,0,-1}; //メイン int main(){ ll n,m; cin>>n>>m; vvl g(n); rep(i,m){ ll u,v; cin>>u>>v; u--,v--; g[u].push_back(v); g[v].push_back(u); } ll k; cin>>k; unordered_set<ll> s; rep(i,k){ ll ss; cin>>ss; ss--; s.insert(ss); } vvl dist(n,vl(5,inf)); dist[0][0]=0; queue<pair<ll,ll>> bfs; bfs.push({0,0}); while(!bfs.empty()){ ll node,renzoku; node=bfs.front().first; renzoku=bfs.front().second; bfs.pop(); rep(i,g[node].size()){ ll nnode=g[node][i]; ll nrenzoku; if(s.count(nnode))nrenzoku=renzoku+1; else nrenzoku=0; if(nrenzoku==5)continue; if(dist[nnode][nrenzoku]==inf){ dist[nnode][nrenzoku]=dist[node][renzoku]+1; bfs.push({nnode,nrenzoku}); } } } ll ans=inf; rep(i,5){ ans=min(dist[n-1][i],ans); } if(ans==inf)cout<<-1<<endl; else cout<<ans<<endl; return 0; }