結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 13:55:52 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 148 ms / 2,000 ms |
コード長 | 2,504 bytes |
コンパイル時間 | 5,576 ms |
コンパイル使用メモリ | 335,224 KB |
実行使用メモリ | 16,992 KB |
最終ジャッジ日時 | 2025-09-06 13:56:10 |
合計ジャッジ時間 | 9,438 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using ll = long long; using ld = long double; ll INF = 2e18; template<typename T> using vc = vector<T>; template<typename T> using vv = vc<vc<T>>; #define MP(a, b) make_pair(a, b) #define nfor(i,s,n) for(ll i=s;i<(ll)n;i++) #define rep(i,n) for(ll i = 0; i < (n); i++) using vl = vc<ll>; using vvl = vv<ll>; using vvvl = vv<vl>; using vvvvl = vv<vvl>; using vs = vc<string>; using vvs = vv<string>; using vb = vc<bool>; using vvb = vv<bool>; using vvvb = vv<vb>; using vld = vc<ld>; using vvld = vv<ld>; using vvvld = vv<vld>; using P = pair<ll, ll>; template<class T>istream& operator>>(istream& i, vc<T>& v) { rep(j, size(v))i >> v[j]; return i; } template<class T> using pq = priority_queue<T, vc<T>>;//大きい順 template<class T> using pq_g = priority_queue<T, vc<T>, greater<T>>;//小さい順 #define pb push_back #define pob pop_back #define all(s) s.begin(),s.end() #define YES std::cout<<"Yes"<<std::endl #define NO std::cout<<"No"<<std::endl #define YN {std::cout<<"Yes"<<std::endl;}else{std::cout<<"No"<<std::endl;} #define dame std::cout<<-1<<std::endl #define pop_cnt(s) ll(popcount(uint64_t(s))) #define yu_qurid(x,y) ((x)*(x)+(y)*(y)) #define mannhattan(x1,x2,y1,y2) (abs(x1-x2)+abs(y1-y2)) #define vc_cout(v){ll n = size(v);rep(i,n)std::cout<<v[i]<<std::endl;} #define vv_cout(v){ll n = size(v);rep(i,n){rep(j,size(v[i])){std::cout<<v[i][j]<<' ';}std::cout<<std::endl;}} using mint = atcoder::modint998244353; // using mint = atcoder::modint1000000007; using vm = vc<mint>; using vvm = vc<vm>; int main(){ ll n, m; cin >> n >> m; vvl g(n); rep(i, m){ ll a, b; cin >> a >> b; a--; b--; g[a].pb(b); g[b].pb(a); } vb b(n, false); ll k; cin >> k; rep(i, k){ ll c; cin >> c; c--; b[c] = true; } vvl dist(n, vl(5, INF)); dist[0][0] = 0; queue<P> q; q.push({0, 0}); while(!q.empty()){ auto [v, s] = q.front(); q.pop(); ll d = dist[v][s]; for(auto nv : g[v]){ ll ns = 0; if(b[nv]) ns = s + 1; if(ns > 4) continue; if(dist[nv][ns] > d + 1){ dist[nv][ns] = d + 1; q.push({nv, ns}); } } } ll ans = INF; rep(i, 5) ans = min(ans, dist[n-1][i]); if(ans == INF){ dame; }else{ cout << ans << endl; } }