結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 13:26:51 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 154 ms / 2,000 ms |
コード長 | 877 bytes |
コンパイル時間 | 3,215 ms |
コンパイル使用メモリ | 288,956 KB |
実行使用メモリ | 14,848 KB |
最終ジャッジ日時 | 2025-09-06 13:27:20 |
合計ジャッジ時間 | 7,211 ms |
ジャッジサーバーID (参考情報) |
judge / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll=long long; int main(){ int n,m; cin>>n>>m; vector<vector<int>> graph(n); for(int i=0;i<m;i++){ int u,v; cin>>u>>v; u--;v--; graph[u].push_back(v); graph[v].push_back(u); } int k; cin>>k; vector<bool> a(n); for(int i=0;i<k;i++){ int t; cin>>t; //cout<<t<<endl; a[t-1]=true; } queue<pair<int,int>> que; que.push(make_pair(0,0)); vector<vector<int>> seen(n,vector<int>(5,-1)); seen[0][0]=0; int ans=1e9; while(!que.empty()){ auto[v,x]=que.front(); //cout<<"v:"<<v<<endl; que.pop(); for(int u:graph[v]){ //cout<<"u:"<<u<<endl; int y=x; if(a[u])y++; else y=0; //cout<<y<<endl; if(y==5||seen[u][y]!=-1)continue; seen[u][y]=seen[v][x]+1; if(u==n-1)ans=min(ans,seen[u][y]); que.push(make_pair(u,y)); } } if(ans<1e9)cout<<ans<<endl; else cout<<-1<<endl; }