結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
![]() |
提出日時 | 2025-09-06 13:38:09 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 240 ms / 2,000 ms |
コード長 | 1,472 bytes |
コンパイル時間 | 6,339 ms |
コンパイル使用メモリ | 332,612 KB |
実行使用メモリ | 20,472 KB |
最終ジャッジ日時 | 2025-09-06 13:38:20 |
合計ジャッジ時間 | 10,580 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; #define FAST_IO \ ios::sync_with_stdio(false); \ cin.tie(0); const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<998244353>; int main() { FAST_IO int N, M; cin >> N >> M; vector<int> U(M), V(M); for (int i = 0; i < M; i++) { cin >> U[i] >> V[i]; U[i]--, V[i]--; } int K; cin >> K; vector<int> A(K); for (int i = 0; i < K; i++) { cin >> A[i]; A[i]--; } set<int> st; for (int i = 0; i < K; i++) { st.insert(A[i]); } vector<vector<int>> G(N); for (int i = 0; i < M; i++) { G[U[i]].push_back(V[i]); G[V[i]].push_back(U[i]); } int m = 5; vector<vector<i64>> dist(N, vector<i64>(m, INF)); using P = pair<i64, pair<int, int>>; priority_queue<P, vector<P>, greater<P>> pq; dist[0][0] = 0; pq.push({0, {0, 0}}); while (!pq.empty()) { auto [d, p] = pq.top(); pq.pop(); auto [v, rem] = p; if (d > dist[v][rem]) continue; for (auto to : G[v]) { int nrem = st.contains(to) ? rem + 1 : 0; if (nrem < m && dist[to][nrem] > d + 1) { dist[to][nrem] = d + 1; pq.push({d + 1, {to, nrem}}); } } } i64 ans = INF; for (int i = 0; i < m; i++) { ans = min(ans, dist[N - 1][i]); } if (ans == INF) ans = -1; cout << ans << endl; }