結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
![]() |
提出日時 | 2025-08-15 14:09:07 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 156 ms / 2,000 ms |
コード長 | 1,288 bytes |
コンパイル時間 | 1,138 ms |
コンパイル使用メモリ | 102,744 KB |
実行使用メモリ | 11,264 KB |
最終ジャッジ日時 | 2025-08-15 14:09:14 |
合計ジャッジ時間 | 6,311 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <iostream> #include <vector> #include <array> #include <queue> using namespace std; constexpr int INF = 1070000000; # pragma GCC optimize("O3") int main(void){ 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); } int K; cin >> K; bool A[N] = {}; for (int i = 0; i < K; i++) { int tmp; cin >> tmp; tmp--; A[tmp] = true; } int dp[N][5]; for (int i = 0; i < N; i++) for (int j = 0; j < 5; j++) dp[i][j] = INF; dp[0][0] = 0; queue<array<int, 2>> q; q.push({0, 0}); while (not q.empty()) { const array<int, 2> now = q.front(); q.pop(); for (int i : G[now[0]]) { const int j = A[i] ? now[1] + 1 : 0; if (j < 5 && dp[now[0]][now[1]] + 1 < dp[i][j]) { dp[i][j] = dp[now[0]][now[1]] + 1; if (i == N - 1) { cout << dp[i][j] << '\n'; return 0; } q.push({i, j}); } } } cout << -1 << '\n'; }