結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
![]() |
提出日時 | 2025-09-07 16:49:22 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,204 bytes |
コンパイル時間 | 3,490 ms |
コンパイル使用メモリ | 290,364 KB |
実行使用メモリ | 822,376 KB |
最終ジャッジ日時 | 2025-09-07 16:49:34 |
合計ジャッジ時間 | 12,171 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | MLE * 1 -- * 2 |
other | -- * 28 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define rep(i,n) for(int i = 0; i < int(n); i++) #define FOR(i,a,b) for(ll i = a; i < (ll)(b); i++) #define all(a) (a).begin(),(a).end() using ll = long long; using VI = vector<int>; using P = pair<int,int>; const long long INF = 1LL << 60; const int DX[] = {1,0,-1,0}; const int DY[] = {0,1,0,-1}; int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); ll n,m; cin >> n >> m; vector<vector<ll>> 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; set<ll> st; rep(i,k){ ll a; cin >> a; st.insert(a); } vector<vector<ll>> dist(n,vector<ll>(5,1e9)); queue<pair<ll,pair<ll,ll>>> q; q.push({0,{0,0}}); dist[0][0] = 0; while(!q.empty()){ ll x = q.front().first; ll cnt = q.front().second.first; ll d = q.front().second.second; q.pop(); for(auto nx : g[x]){ ll nc = cnt; if(st.count(nx)){ nc++; } else nc = 0; if(nc < 5 && dist[nx][nc] > d+1){ q.push({nx,{nc,d+1}}); dist[nx][cnt] = d+1; } } } ll ans = *min_element(all(dist[n-1])); if(ans == 1e9) cout << -1 << endl; else cout << ans << endl; return 0; }