結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 13:44:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 814 ms / 2,000 ms |
コード長 | 3,020 bytes |
コンパイル時間 | 4,503 ms |
コンパイル使用メモリ | 260,224 KB |
実行使用メモリ | 111,672 KB |
最終ジャッジ日時 | 2025-09-06 13:44:41 |
合計ジャッジ時間 | 15,430 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
# include <bits/stdc++.h> # include <atcoder/modint> # include <atcoder/segtree> # include <atcoder/lazysegtree> # include <atcoder/dsu> # include <atcoder/scc> # include <atcoder/string> # include <atcoder/twosat> # include <atcoder/math> # include <atcoder/convolution> //# include <regex> using namespace std; typedef long long ll; typedef long double ld; typedef vector<int> vi; typedef vector<vector<int>> vvi; typedef vector<vector<vector<int>>> vvvi; typedef vector<long long> vl; typedef vector<vector<long long>> vvl; typedef vector<vector<vector<long long>>> vvvl; typedef vector<bool> vb; typedef vector<vector<bool>> vvb; typedef vector<vector<vector<bool>>> vvvb; #define rep(i,n) for(int i=0;i<n;i++) #define reps(i,m,n) for(int i=m;i<n;i++) #define repl(i,n) for(ll i=0;i<n;i++) #define repsl(i,m,n) for(ll i=m;i<n;i++) #define repr(i,n) for(int i=n-1;i>=0;i--) #define repsr(i,m,n) for(int i=n-1;i>=m;i--) #define replr(i,n) for(ll i=n-1;i>=0;i--) #define repslr(i,m,n) for(ll i=n-1;i>=m;i--) #define sksort(x) sort(x.begin(), x.end()) #define sksortr(x) sort(x.rbegin(), x.rend()) #define disp(x) cout << x << endl #define disps(x) cout << x << " " #define dispe cout << endl #define dispv(x) for(ll xqzj=0;xqzj<(ll)x.size();xqzj++){disps(x[xqzj]);}dispe #define dispvv(x) for(ll xqzi=0;xqzi<(ll)x.size();xqzi++){dispv(x[xqzi]);} #define dispvm(x) for(ll xqzj=0;xqzj<(ll)x.size();xqzj++){disps(x[xqzj].val());}dispe #define dispvvm(x) for(ll xqzi=0;xqzi<(ll)x.size();xqzi++){dispvm(x[xqzi]);} #define dispy cout << "Yes" << endl #define dispn cout << "No" << endl #define dispyn(x) if(x)dispy;else dispn #define dispd cout << std::setprecision(20) #define inp(x) int x;cin>>x #define inpl(x) ll x;cin>>x #define inps(x) string x;cin>>x #define allv(x) (x).begin(),(x).end() #define allrv(x) (x).rbegin(),(x).rend() #define imax(x,y) x=max(x,y) #define imin(x,y) x=min(x,y) template <class T> using priority_queue_asc = std::priority_queue<T,std::vector<T>,std::greater<T>>; using mint = atcoder::modint998244353; //using mint = atcoder::modint1000000007; int main(){ inp(n); inp(m); vi u(m); vi v(m); rep(i,m)cin>>u[i]>>v[i]; rep(i,m)u[i]--; rep(i,m)v[i]--; inp(k); vb b(n); rep(i,k){ inp(a); b[a-1]=true; } vector<unordered_set<int>> g(n*5); rep(i,m){ if(b[u[i]]){ rep(j,4)g[j*n+v[i]].insert((j+1)*n+u[i]); }else{ rep(j,5)g[j*n+v[i]].insert(u[i]); } if(b[v[i]]){ rep(j,4)g[j*n+u[i]].insert((j+1)*n+v[i]); }else{ rep(j,5)g[j*n+u[i]].insert(v[i]); } } queue<pair<int,int>> q; q.push({0,0}); vb w(n*5); w[0]=true; int ans=-1; while(q.size()){ pair<int,int> p=q.front(); q.pop(); if(p.first%n==n-1){ ans=p.second; break; } for(int i:g[p.first])if(!w[i]){ w[i]=true; q.push({i,p.second+1}); } } disp(ans); }