結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
![]() |
提出日時 | 2025-09-06 13:49:34 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 288 ms / 2,000 ms |
コード長 | 1,644 bytes |
コンパイル時間 | 3,914 ms |
コンパイル使用メモリ | 291,572 KB |
実行使用メモリ | 37,032 KB |
最終ジャッジ日時 | 2025-09-06 13:49:58 |
合計ジャッジ時間 | 8,734 ms |
ジャッジサーバーID (参考情報) |
judge / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = int64_t; constexpr ll INF = (1LL << 60) - 1; ll N, M; vector<ll> U, V; vector<vector<ll>> G; ll K; vector<bool> A; void input() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> N >> M; U.resize(M), V.resize(M); for (ll i=0; i<M; ++i) { cin >> U[i] >> V[i]; --U[i], --V[i]; } cin >> K; A.resize(N, false); for (ll i=0; i<K; ++i) { ll a; cin >> a; A[a-1] = true; } } vector<bool> VISITED; vector<ll> C; void bfs(ll start) { C.assign(N*5, INF); C[start] = 0; deque<ll> que; que.emplace_back(start); while (!que.empty()) { ll v = que.front(); que.pop_front(); for (const auto& e : G[v]) { if (C[e] != INF) continue; C[e] = C[v] + 1; que.emplace_back(e); } } } void solve() { G.resize(N*5); for (ll i=0; i<M; ++i) { if (A[V[i]]) { for (ll j=0; j<4; ++j) { G[U[i]+N*j].emplace_back(V[i]+N*(j+1)); } } else { for (ll j=0; j<=4; ++j) { G[U[i]+N*j].emplace_back(V[i]); } } if (A[U[i]]) { for (ll j=0; j<4; ++j) { G[V[i]+N*j].emplace_back(U[i]+N*(j+1)); } } else { for (ll j=0; j<=4; ++j) { G[V[i]+N*j].emplace_back(U[i]); } } } bfs(0); if (C[N-1] == INF) cout << -1 << "\n"; else cout << C[N-1] << "\n"; } int main() { input(); solve(); return 0; } /* 考察 */