結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 14:20:55 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 170 ms / 2,000 ms |
コード長 | 2,848 bytes |
コンパイル時間 | 2,610 ms |
コンパイル使用メモリ | 210,172 KB |
実行使用メモリ | 15,488 KB |
最終ジャッジ日時 | 2025-09-06 14:21:23 |
合計ジャッジ時間 | 6,616 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0; i<(n); i++) #define rep1(i,n) for(int i=1; i<=(n); i++) #define sz(x) int(x.size()) #define all(x) (x).begin(),(x).end() #define lINF ll(2e18)//LONG_LONG_MAX //ll #define iINF int(2e9+100)//INT_MAX //int #define yes "Yes" #define no "No" #define kotae cout<<ans<<endl; #define dame { puts("-1"); return 0;} #define dame0 { puts("0"); return 0;} #define yn {puts("Yes");}else{puts("No");} #define db cout<<'@'<<endl; #define el cout<<'\n'; #define pc(x) __builtin_popcount(x) #define pcl(x) __builtin_popcountll(x) using ll=long long; using ull=unsigned long long; using Pii=pair<int,int>; using Pil=pair<int,ll>; using Pli=pair<ll,int>; using Pll=pair<ll,ll>; using Pci=pair<char,int>; using Pcl=pair<char,ll>; template <typename T> using pqg = priority_queue<T,vector<T>,greater<T>>; using vi=vector<int>; using vi2=vector<vector<int>>; using vi3=vector<vector<vector<int>>>; using vl=vector<ll>; using vl2=vector<vector<ll>>; using vl3=vector<vector<vector<ll>>>; using vs=vector<string>; using vpii=vector<Pii>; using vpil=vector<Pil>; using vpci=vector<Pci>; using vpcl=vector<Pcl>; using Ti=tuple<int,int,int>; using vti=vector<Ti>; void coutdouble(double x) { printf("%.10f\n", x); } void coutvi(vi vec) { for (int k : vec)cout << k << ' '; cout << endl; return; } void coutvl(vl vec) { for (ll k : vec)cout << k << ' '; cout << endl; return; } void coutseti(set<int> st) { for (int k : st)cout << k << ' '; cout << endl; return; } void coutsetl(set<ll> st) { for (ll k : st)cout << k << ' '; cout << endl; return; } void chmax(int &a, int b){ a = max(a, b); return;} void chmin(int &a, int b){ a = min(a, b); return;} void chmaxl(ll &a, ll b){ a = max(a, b); return;} void chminl(ll &a, ll b){ a = min(a, b); return;} void rev(vi &a){ reverse(all(a)); return;} template <typename T> void srt(T &a){ sort(all(a)); return;} template <typename T> void srtr(T &a){ sort(a.rbegin(),a.rend()); return;} void solve(); int main() { int t = 1; //cin >> t; rep(i,t) solve(); return 0; } void solve() { int n,m; cin >> n >> m; vi2 g(n); rep(i,m){ int u,v; cin >> u >> v; u--; v--; g[u].push_back(v); g[v].push_back(u); } queue<Pii>q; vi2 dist(n,vi(5,-1)); rep(i,5)dist[0][i] = 0; int k; cin >> k; vl ok(n,true); rep(i,k){ int a; cin >> a; a--; ok[a] = false; } q.emplace(0,0); while(!q.empty()){ auto[u,c] = q.front(); q.pop(); for(int v:g[u]){ if(!ok[v] && c == 4) continue; int nc = 0; if(ok[v]) nc = 0; else nc = c+1; if(dist[v][nc] != -1) continue; dist[v][nc] = dist[u][c]+1; q.emplace(v,nc); } } int ans = iINF; rep(i,5) if(dist[n-1][i] != -1) chmin(ans, dist[n-1][i]); if(ans == iINF) ans = -1; kotae return; }