結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 15:06:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 269 ms / 2,000 ms |
コード長 | 1,520 bytes |
コンパイル時間 | 3,078 ms |
コンパイル使用メモリ | 224,792 KB |
実行使用メモリ | 19,168 KB |
最終ジャッジ日時 | 2025-09-06 15:06:21 |
合計ジャッジ時間 | 8,283 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; #define rep(i, a, n) for (int i = a; i < (int)(n); i++) using ll = long long; const ll INF = 1ll << 60; int main() { ll n, m; cin >> n >> m; vector<vector<ll>> graph(n); rep(i, 0, m) { ll u, v; cin >> u >> v; u--; v--; graph[u].push_back(v); graph[v].push_back(u); } ll iwi; cin >> iwi; set<ll> exist; rep(_, 0, iwi) { ll x; cin >> x; x--; exist.insert(x); } vector<vector<ll>> dist(n, vector<ll>(5, INF)); dist[0][0] = 0; queue<pair<ll, ll>> q; q.push({0, 0}); while (!q.empty()) { auto [pos, seen] = q.front(); q.pop(); for (auto &nex : graph[pos]) { ll nex_seen = seen; if (exist.count(nex)) { nex_seen++; } else { nex_seen = 0; } if (nex_seen >= 5) { continue; } ll new_dist = dist[pos][seen] + 1; if (new_dist < dist[nex][nex_seen]) { dist[nex][nex_seen] = new_dist; q.push({nex, nex_seen}); } } } ll ans = INF; rep(i, 0, 5) { ans = min(ans, dist[n - 1][i]); } if (ans == INF) { cout << -1 << endl; } else { cout << ans << endl; } }