結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
![]() |
提出日時 | 2025-09-07 17:07:09 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 81 ms / 2,000 ms |
コード長 | 1,207 bytes |
コンパイル時間 | 3,098 ms |
コンパイル使用メモリ | 288,956 KB |
実行使用メモリ | 16,888 KB |
最終ジャッジ日時 | 2025-09-07 17:07:16 |
合計ジャッジ時間 | 6,086 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 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; vector<bool> is_iwai(n,0); rep(i,k){ ll a; cin >> a; is_iwai[a-1] = true; } vector<vector<ll>> dist(n,vector<ll>(5,1e18)); queue<pair<ll,ll>> q; q.push({0,0}); dist[0][0] = 0; while(!q.empty()){ auto [x,cnt] = q.front(); q.pop(); for(auto nx : g[x]){ ll next_cnt = cnt; if(is_iwai[nx]) next_cnt++; else next_cnt = 0; if(next_cnt >= 5) continue; if(dist[nx][next_cnt] > dist[x][cnt] + 1){ dist[nx][next_cnt] = dist[x][cnt] + 1; q.push({nx,next_cnt}); } } } ll ans = *min_element(all(dist[n-1])); if(ans == 1e18) cout << -1 << endl; else cout << ans << endl; return 0; }