結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 13:39:19 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 101 ms / 2,000 ms |
コード長 | 2,669 bytes |
コンパイル時間 | 3,933 ms |
コンパイル使用メモリ | 289,364 KB |
実行使用メモリ | 17,016 KB |
最終ジャッジ日時 | 2025-09-06 13:40:06 |
合計ジャッジ時間 | 6,552 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#ifndef ONLINE_JUDGE #define _GLIBCXX_DEBUG //[]で配列外参照をするとエラーにしてくれる。上下のやつがないとTLEになるので注意 ABC311Eのサンプル4みたいなデバック中のTLEは防げないので注意 #endif #include <bits/stdc++.h> #include <algorithm> #include <cmath> // M_PIを使用するため using namespace std; using ll = long long; using ld = long double; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) #define rrep(i, n) for (ll i = (ll)n - 1; i >= 0; --i) const ll INF = (1LL << 62); const ll null = -1LL; template <typename T> using vc = vector<T>; // prioriy_queueに必要なのでここにこれ書いてます template <typename T> using vv = vc<vc<T>>; template <typename T> using vvv = vv<vc<T>>; using vl = vc<ll>; using vvl = vv<ll>; using vvvl = vv<vl>; using vvvvl = vv<vvl>; using vs = vc<string>; using vvs = vv<string>; using vb = vc<bool>; using vvb = vc<vb>; using P = pair<ll, ll>; template <class T> istream &operator>>(istream &i, vc<T> &v) { rep(j, size(v)) i >> v[j]; return i; } // それぞれ「下,上,右,左」に対応 int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; #define nall(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() template <class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template <class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } #define pb push_back #define eb emplace_back #define em emplace #define pob pop_back #define next_p(v) next_permutation(v.begin(), v.end()) void solve() { ll n, m; cin >> n >> m; vvl G(n); rep(_,m) { ll u, v; cin >> u >> v; --u, --v; G[u].pb(v); G[v].pb(u); } ll k; cin >> k; vb isyiwiy(n,false); rep(_,k) { ll pos; cin >> pos; isyiwiy[pos-1] = true; } vvl dist(n,vl(5,INF)); dist[0][0] = 0; queue<P> q; q.em(0,0); while (q.size()) { auto [v,md] = q.front(); q.pop(); for (ll nv : G[v]) { ll nmd = md; if (isyiwiy[nv]) nmd++; else nmd = 0; if (nmd >= 5) continue; if (dist[nv][nmd] != INF) continue; dist[nv][nmd] = dist[v][md] + 1ll; q.em(nv,nmd); } } ll ans = INF; rep(i,5) chmin(ans,dist[n-1][i]); cout << (ans < INF? ans : -1) << endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll testcases = 1ll; // cin >> testcases; rep(_, testcases) solve(); return 0; }