結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
![]() |
提出日時 | 2025-09-06 18:02:21 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 140 ms / 2,000 ms |
コード長 | 1,433 bytes |
コンパイル時間 | 3,225 ms |
コンパイル使用メモリ | 288,724 KB |
実行使用メモリ | 14,720 KB |
最終ジャッジ日時 | 2025-09-06 18:02:29 |
合計ジャッジ時間 | 7,027 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #define debug(x) cerr << #x << " = " << (x) << "\n" #else #define debug(x) void(0) #endif typedef long long ll; typedef long double ld; typedef pair<int, int> Pii; typedef pair<ll, ll> Pll; template <typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (int i = 0; i < (int)v.size(); i++) os << v[i] << (i + 1 == (int)v.size() ? "" : " "); return os; } template <typename T> istream &operator>>(istream &is, vector<T> &v) { for (int i = 0; i < (int)v.size(); i++) is >> v[i]; return is; } //////////////////////////////////////////////////////////// int main() { 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[U].push_back(V); G[V].push_back(U); } vector<bool> exist(N, false); int K; cin >> K; for (int i = 0; i < K; i++) { int A; cin >> A; exist[A - 1] = true; } vector dist(N, vector<int>(5, 1e9)); queue<Pii> Q; Q.push({0, 0}); dist[0][0] = 0; while (!Q.empty()) { auto [now, val] = Q.front(); Q.pop(); for (auto to : G[now]) { int nval = exist[to] ? val + 1 : 0; if (nval > 4 || dist[to][nval] != (int)1e9) continue; dist[to][nval] = dist[now][val] + 1; Q.push({to, nval}); } } int ans = *min_element(dist[N - 1].begin(), dist[N - 1].end()); cout << (ans == (int)1e9 ? -1 : ans) << "\n"; return 0; }