結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 13:59:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 58 ms / 2,000 ms |
コード長 | 1,252 bytes |
コンパイル時間 | 2,434 ms |
コンパイル使用メモリ | 203,160 KB |
実行使用メモリ | 13,824 KB |
最終ジャッジ日時 | 2025-09-06 13:59:50 |
合計ジャッジ時間 | 4,730 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, s, t) for (ll i = s; i < (ll)(t); i++) #define all(x) begin(x), end(x) template <class T> bool chmin(T& x, T y) { return x > y ? (x = y, true) : false; } template <class T> bool chmax(T& x, T y) { return x < y ? (x = y, true) : false; } struct io_setup { io_setup() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); } } io_setup; void solve() { int n, m; cin >> n >> m; vector<vector<int>> g(n); rep(i, 0, m) { int u, v; cin >> u >> v; u--, v--; g[u].push_back(v); g[v].push_back(u); } int k; cin >> k; vector<int> wall(n, 0); rep(i, 0, k) { int a; cin >> a; a--; wall[a] = 1; } vector<vector<int>> dist(5, vector<int>(n, -1)); dist[0][0] = 0; vector<array<int, 2>> vp = {{0, 0}}; rep(i, 0, vp.size()) { auto [d, nw] = vp[i]; if (nw == n - 1) { cout << dist[d][nw] << "\n"; return; } for (int nx : g[nw]) { int nd = d; if (wall[nx]) nd++; else nd = 0; if (nd >= 5) continue; if (dist[nd][nx] != -1) continue; dist[nd][nx] = dist[d][nw] + 1; vp.push_back({nd, nx}); } } cout << "-1\n"; } int main() { int t = 1; // cin >> t; while (t--) solve(); }