結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 14:09:23 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 97 ms / 2,000 ms |
コード長 | 3,765 bytes |
コンパイル時間 | 3,179 ms |
コンパイル使用メモリ | 289,268 KB |
実行使用メモリ | 17,784 KB |
最終ジャッジ日時 | 2025-09-06 14:09:36 |
合計ジャッジ時間 | 6,000 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
// 2025 9/6 // 2025 9/6 #include <bits/stdc++.h> using namespace std; #define int long long const int mod = 998244353; template <class T> void out(vector<vector<T>> v) { for (int i = 0; i < (int)v.size(); i++) for (int j = 0; j < (int)v.at(i).size(); j++) { cout << v.at(i).at(j) << " "; if (j == (int)v.at(i).size() - 1) cout << endl; } } template <class T> void out2(vector<vector<vector<T>>> v) { cout << "-----------------" << endl; for (int i = 0; i < (int)v.size(); i++) { cout << "i:" << i << endl; for (int j = 0; j < (int)v.at(i).size(); j++) for (int k = 0; k < (int)v.at(i).at(j).size(); k++) { cout << v.at(i).at(j).at(k) << " "; if (k == (int)v.at(i).at(j).size() - 1) cout << endl; } cout << "-----------------" << endl; } } template <class T> void out3(vector<vector<vector<T>>> v) { cout << "-----------------" << endl; for (int k = 0; k < (int)v.at(0).at(0).size(); k++) { cout << "k:" << k << endl; for (int i = 0; i < (int)v.size(); i++) { for (int j = 0; j < (int)v.at(i).size(); j++) { cout << v.at(i).at(j).at(k) << " "; if (j == v.at(i).size() - 1) cout << endl; } } cout << "-----------------" << endl; } } template <class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } template <class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } int power(int x, int n, int mod) { int ret = 1; while (n > 0) { if (n & 1) { ret *= x; if (mod > 0) ret %= mod; } x *= x; if (mod > 0) x %= mod; n >>= 1; } return ret; } signed main(void) { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<vector<int>> g(n); for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; u--; v--; g.at(u).push_back(v); g.at(v).push_back(u); } int k; cin >> k; vector<int> is(n, 0); for (int i = 0; i < k; i++) { int a; cin >> a; a--; is.at(a) = 1; } vector<vector<int>> dist(n, vector<int>(5, -1)); // i番目の頂点で、岩井星人に連続してj回あっている場合の最短経路 queue<pair<int, int>> que; // (頂点番号, 連続して岩井星人に会っている回数) dist.at(0).at(0) = 0; que.push({0, 0}); while (!que.empty()) { pair p = que.front(); que.pop(); for (int u : g.at(p.first)) { if (is.at(u) == 1) { if (p.second + 1 < 5 && dist.at(u).at(p.second + 1) == -1) { dist.at(u).at(p.second + 1) = dist.at(p.first).at(p.second) + 1; que.push({u, p.second + 1}); } } else { if (dist.at(u).at(0) == -1) { dist.at(u).at(0) = dist.at(p.first).at(p.second) + 1; que.push({u, 0}); } } } } int ans = INT_MAX; for (int i = 0; i < 5; i++) { if (dist.at(n - 1).at(i) == -1) continue; chmin(ans, dist.at(n - 1).at(i)); } if (ans == INT_MAX) cout << -1 << endl; else cout << ans << endl; }