結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
![]() |
提出日時 | 2025-09-06 13:26:32 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 102 ms / 2,000 ms |
コード長 | 1,806 bytes |
コンパイル時間 | 3,174 ms |
コンパイル使用メモリ | 285,212 KB |
実行使用メモリ | 14,920 KB |
最終ジャッジ日時 | 2025-09-06 13:27:05 |
合計ジャッジ時間 | 6,109 ms |
ジャッジサーバーID (参考情報) |
judge / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define ll long long const long long mod=998244353; const long long hmod=46216567629137; int main(){ cin.tie(0)->sync_with_stdio(0); cout.tie(0); int N,M; cin>>N>>M; int U[M+1],V[M+1]; vector<int>G[N+1]; for(int i=1;i<=M;i++){ cin>>U[i]>>V[i]; G[U[i]].push_back(V[i]); G[V[i]].push_back(U[i]); } bool yiwiy[N+1]; for(int i=1;i<=N;i++) yiwiy[i]=0; int K; cin>>K; int A[K+1]; for(int i=1;i<=K;i++){ cin>>A[i]; yiwiy[A[i]]=1; } ll dist[N+1][5]; bool already[N+1][5]; for(int i=1;i<=N;i++){ rep(j,5){ dist[i][j]=2e18; already[i][j]=0; } } queue<pair<int,int>>que; que.push({1,0}); dist[1][0]=0; while(!que.empty()){ int pos=que.front().first,joutai=que.front().second; que.pop(); if(already[pos][joutai]) continue; already[pos][joutai]=1; for(int i=0;i<G[pos].size();i++){ int nex=G[pos][i]; if(yiwiy[nex]){ if(joutai==4) continue; if(already[nex][joutai+1]) continue; if(dist[nex][joutai+1]>dist[pos][joutai]+1){ dist[nex][joutai+1]=dist[pos][joutai]+1; que.push({nex,joutai+1}); } } else{ if(already[nex][0]) continue; if(dist[nex][0]>dist[pos][joutai]+1){ dist[nex][0]=dist[pos][joutai]+1; que.push({nex,0}); } } } } ll ans=2e18; rep(i,5) ans=min(ans,dist[N][i]); if(ans==2e18) cout<<"-1\n"; else cout<<ans<<"\n"; }