結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
![]() |
提出日時 | 2025-09-06 13:33:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 130 ms / 2,000 ms |
コード長 | 1,043 bytes |
コンパイル時間 | 2,199 ms |
コンパイル使用メモリ | 205,556 KB |
実行使用メモリ | 13,824 KB |
最終ジャッジ日時 | 2025-09-06 13:33:42 |
合計ジャッジ時間 | 5,608 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
//N連続岩井. #include <bits/stdc++.h> using namespace std; #define int long long int N,M; int INF = 1e18; signed main(){ cin>>N>>M; vector<vector<int>> G(N); for(int i = 0; i < M; i++){ int u,v; cin>>u>>v; u--; v--; G[u].push_back(v); G[v].push_back(u); } vector<vector<int>> dist(5,vector<int>(N,INF)); int K; cin>>K; vector<bool> A(N,false); for(int i = 0; i < K; i++){ int p; cin>>p; p--; A[p] = true; } queue<pair<int,int>> Q; Q.push({0,0}); dist[0][0] = 0; while(!Q.empty()){ int ren = Q.front().first; int pos = Q.front().second; Q.pop(); for(int i:G[pos]){ if(A[i]){ if(ren+1 >= 5) continue; if(dist[ren+1][i] != INF) continue; dist[ren+1][i] = dist[ren][pos] + 1; Q.push({ren+1,i}); } else{ if(dist[0][i] != INF) continue; dist[0][i] = dist[ren][pos] + 1; Q.push({0,i}); } } } int ans = min({dist[0][N-1],dist[1][N-1],dist[2][N-1],dist[3][N-1],dist[4][N-1]}); ans == INF ? cout << -1 << "\n" : cout << ans << "\n"; }