結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
![]() |
提出日時 | 2025-09-06 13:30:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 116 ms / 2,000 ms |
コード長 | 3,359 bytes |
コンパイル時間 | 4,610 ms |
コンパイル使用メモリ | 261,680 KB |
実行使用メモリ | 19,012 KB |
最終ジャッジ日時 | 2025-09-06 13:30:33 |
合計ジャッジ時間 | 7,840 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; #define ALL(a) (a).begin(), (a).end() #define rep(i, n) for (ll i = 0; i < (n); ++i) #define rrep(i, n) for (ll i = (n) - 1; i >= 0; --i) #define foreach(i, n) for (auto i : (n)) #define chmax(a, b) a = max(a, b) #define chmin(a, b) a = min(a, b) #define popcount __builtin_popcountll using mint = modint998244353; using mint1 = modint1000000007; template <typename K, typename V> using umap = std::unordered_map<K, V>; template <typename K> using uset = std::unordered_set<K>; // 参考元 : https://qiita.com/ganyariya/items/df35d253726269bda436 struct HashPair { //注意 constがいる template<class T1, class T2> size_t operator()(const pair<T1, T2> &p) const { //first分をハッシュ化する auto hash1 = hash<T1>{}(p.first); //second分をハッシュ化する auto hash2 = hash<T2>{}(p.second); //重複しないようにハッシュ処理 size_t seed = 0; seed ^= hash1 + 0x9e3779b9 + (seed << 6) + (seed >> 2); seed ^= hash2 + 0x9e3779b9 + (seed << 6) + (seed >> 2); return seed; } }; template <typename X, typename Y> using pair_map = unordered_map<pair<X, Y>, ll, HashPair>; template <typename X, typename Y> using pair_set = unordered_set<pair<X, Y>, HashPair>; template <typename T> using v = vector<T>; template <typename T> using vv = v<v<T>>; template <typename T> using vvv = vv<v<T>>; template <typename T, typename U> using P = pair<T, U>; using grid = vector<vector<char>>; using graph = vector<vector<int>>; using vi = vector<int>; using vvi = vector<vector<int>>; using vvvi = vector<vector<vector<int>>>; using vl = vector<ll>; using vvl = vector<vector<ll>>; using vvvl = vector<vector<vector<ll>>>; using vm = vector<mint>; using vvm = vector<vector<mint>>; using vvvm = vector<vector<vector<mint>>>; using vm1 = vector<mint1>; using vvm1 = vector<vector<mint1>>; using vvvm1 = vector<vector<vector<mint1>>>; using vld = vector<ld>; using vvld = vector<vector<ld>>; using vvvld = vector<vector<vector<ld>>>; using vb = vector<bool>; using vvb = vector<vector<bool>>; using vs = vector<string>; using vvs = vector<vector<string>>; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll n, m; cin >> n >> m; graph g(n); rep(i, m) { ll u, v; cin >> u >> v; u--; v--; g[u].push_back(v); g[v].push_back(u); } ll k; cin >> k; uset<ll> iwai; rep(i, k) { ll a; cin >> a; a--; iwai.insert(a); } vvl dist(n, vl(5, -1)); queue<P<ll, ll>> que; dist[0][0] = 0; que.push({0, 0}); while (!que.empty()) { auto [v, iwi] = que.front(); que.pop(); foreach(nv, g[v]) { ll next_iwi = iwi; if (iwai.count(nv)) { next_iwi++; } else { next_iwi = 0; } if (next_iwi > 4) continue; if (dist[nv][next_iwi] != -1) continue; dist[nv][next_iwi] = dist[v][iwi] + 1; que.push({nv, next_iwi}); } } cout << dist[n - 1][0] << "\n"; return 0; }