結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 13:23:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 53 ms / 2,000 ms |
コード長 | 1,875 bytes |
コンパイル時間 | 2,483 ms |
コンパイル使用メモリ | 207,708 KB |
実行使用メモリ | 11,760 KB |
最終ジャッジ日時 | 2025-09-06 13:24:16 |
合計ジャッジ時間 | 4,600 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; template <class T> struct csr { using itr = typename std::vector<T>::iterator; struct Node { itr st, en; itr begin() { return st; } itr end() { return en; } int size() { return en - st; } T operator[](int p){ return st[p]; } }; const int N; std::vector<int> start; std::vector<T> E; std::vector<std::pair<int,T>> edge; csr(int n) : N(n), start(n + 1) {} void add_edge(int u, T v){ assert(0 <= u && u < N); start[u + 1]++; edge.emplace_back(u, v); } void build(){ E.resize(edge.size()); for(int i = 0; i < N; i++) start[i + 1] += start[i]; auto cnt = start; for(auto [u, v] : edge) E[cnt[u]++] = v; } Node operator[](int p) { return Node{E.begin() + start[p], E.begin() + start[p + 1]}; } }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; csr<int> g(n); for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; u--, v--; g.add_edge(u, v); g.add_edge(v, u); } g.build(); int k; cin >> k; vector<bool> tb(n); for(int i = 0; i < k; i++){ int v; cin >> v; tb[v - 1] = true; } vector dp(n, vector<int>(5, 1 << 30)); queue<pair<int,int>> que; dp[0][0] = 0; que.emplace(0, 0); while(!que.empty()){ auto [v, s] = que.front(); que.pop(); for(auto u : g[v]){ int ns = tb[u] ? s + 1 : 0; if(ns >= 5 || dp[v][s] + 1 >= dp[u][ns]) continue; dp[u][ns] = dp[v][s] + 1; que.emplace(u, ns); } } int ans = *min_element(dp[n - 1].begin(), dp[n - 1].end()); if(ans >> 30) ans = -1; cout << ans << '\n'; }