結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 19:35:03 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 96 ms / 2,000 ms |
コード長 | 1,277 bytes |
コンパイル時間 | 3,747 ms |
コンパイル使用メモリ | 284,008 KB |
実行使用メモリ | 15,232 KB |
最終ジャッジ日時 | 2025-09-06 19:35:10 |
合計ジャッジ時間 | 6,866 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; // #include<atcoder/all> // using mint = atcoder::modint998244353; using ld = long double; #define fi first #define se second #define all(x) x.begin(),x.end() #define rep(i,n) for(int i=0;i<(int)(n);++i) template<typename T>bool chmin(T&a,T b){return b<a?(a=b,1):0;} template<typename T>bool chmax(T&a,T b){return b>a?(a=b,1):0;} int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N,M; cin>>N>>M; vector<vector<int>> G(N); rep(i,M){ int u,v; cin>>u>>v; u--;v--; G[u].push_back(v); G[v].push_back(u); } int K; cin>>K; vector<int> A(N,0); rep(i,K){ int a; cin>>a; a--; A[a]=1; } queue<pair<int,int>> q; vector dp(N,vector<int>(5,1e9)); dp[0][0]=0; q.push({0,0}); while(!q.empty()){ auto [v,k]=q.front(); q.pop(); for(int e: G[v]){ int x=k; if(A[e]) x++; else x=0; if(x==5) continue; if(dp[e][x]!=1e9) continue; dp[e][x]=dp[v][k]+1; q.push({e,x}); } } int ans=1e9; rep(i,5) chmin(ans, dp[N-1][i]); if(ans==1e9) ans=-1; cout<<ans<<"\n"; }