結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
![]() |
提出日時 | 2025-09-06 14:15:27 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 67 ms / 2,000 ms |
コード長 | 1,252 bytes |
コンパイル時間 | 3,617 ms |
コンパイル使用メモリ | 289,084 KB |
実行使用メモリ | 11,708 KB |
最終ジャッジ日時 | 2025-09-06 14:16:01 |
合計ジャッジ時間 | 5,619 ms |
ジャッジサーバーID (参考情報) |
judge / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #ifdef LOCAL #include <debug.hpp> #else #define debug(...) #endif constexpr int INF = (1 << 30) - 1; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); 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].emplace_back(V); G[V].emplace_back(U); } int K; cin >> K; vector<int> isiwi(N); for (int i = 0; i < K; i++) { int A; cin >> A, A--; isiwi[A] = true; } vector dist(5, vector<int>(N, INF)); queue<pair<int, int>> que; dist[0][0] = 0; que.emplace(0, 0); while (!que.empty()) { auto [iwi, v] = que.front(); que.pop(); for (auto u : G[v]) { int niwi = isiwi[u] ? iwi + 1 : 0; if (niwi >= 5) continue; if (dist[niwi][u] != INF) continue; dist[niwi][u] = dist[iwi][v] + 1; que.emplace(niwi, u); } } int ans = INF; for (int i = 0; i < 5; i++) { ans = min(ans, dist[i][N - 1]); } cout << (ans == INF ? -1 : ans) << "\n"; }