結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 14:02:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 117 ms / 2,000 ms |
コード長 | 2,755 bytes |
コンパイル時間 | 2,163 ms |
コンパイル使用メモリ | 208,904 KB |
実行使用メモリ | 18,556 KB |
最終ジャッジ日時 | 2025-09-06 14:02:57 |
合計ジャッジ時間 | 5,083 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#ifndef ONLINE_JUDGE #define _GLIBCXX_DEBUG #endif #include <bits/stdc++.h> using namespace std; // #include <atcoder/all> // using namespace atcoder; using ll = long long; // 2^63-1まで 負の値は可 using ull = unsigned long long; // 0<= ull <=2^64-1の範囲 負の値は不可 using vl = vector<ll>; using vvl = vector<vl>; using P = pair<ll, ll>; template <typename T> using MNPQ = priority_queue<T, vector<T>, greater<T>>; template <typename T> using MXPQ = priority_queue<T, vector<T>, less<T>>; #define rep(i, n) for (int i = 0; i < n; i++) #define srep(i, s, n) for (int i = s; i < n; i++) #define rrep(i, s, n) for (int i = s; i > n; i--) #define chmax(x, y) x = max(x, y) #define chmin(x, y) x = min(x, y) #define nall(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define vunique(v) v.erase(unique(nall(v)), v.end()) #define IN(a, x) find(nall(a), x) != a.end() #define YN(flg) cout << (flg ? "Yes" : "No") << "\n" #define out_grid(x, y, h, w) !(0 <= x && x < h && 0 <= y && y < w) #define lmd(...) [&](__VA_ARGS__) #define debug(x) cerr << #x << " = " << x << endl; const ll INF = 2e18; template <typename T> istream& operator>>(istream& is, vector<T>& a) { for (auto& x : a) is >> x; return is; } template <typename T> ostream& operator<<(ostream& os, vector<T>& a) { for (int i = 0; i < (int)a.size(); i++) os << a[i] << " "; return os; } template <typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1, T2>& p) { os << "{" << p.first << "," << p.second << "}"; return os; } template <typename K, typename V> ostream& operator<<(ostream& os, map<K, V>& a) { for (auto& [k, v] : a) os << "{key:" << k << ", item:" << v << "} "; return os; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); ll n, m; cin >> n >> m; vvl graph(n + 1); rep(i, m) { ll u, v; cin >> u >> v; graph[u].push_back(v); graph[v].push_back(u); } ll k; cin >> k; vector<bool> iwai(n + 1); rep(i, k) { ll a; cin >> a; iwai[a] = 1; } vvl dist(n + 1, vl(6, INF)); queue<P> que; dist[1][0] = 0; que.emplace(1, 0); while (!que.empty()) { auto [v, cnt] = que.front(); que.pop(); for (auto i : graph[v]) { ll ncnt = cnt; if (iwai[i]) ncnt++; else ncnt = 0; if (ncnt == 5) continue; if (dist[i][ncnt] != INF) continue; dist[i][ncnt] = dist[v][cnt] + 1; que.emplace(i, ncnt); } } ll ans = INF; rep(i, 5) chmin(ans, dist[n][i]); cout << (ans == INF ? -1 : ans) << endl; return 0; }