結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 13:34:58 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 113 ms / 2,000 ms |
コード長 | 1,756 bytes |
コンパイル時間 | 1,868 ms |
コンパイル使用メモリ | 176,056 KB |
実行使用メモリ | 14,844 KB |
最終ジャッジ日時 | 2025-09-06 13:35:03 |
合計ジャッジ時間 | 4,633 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
コンパイルメッセージ
main.cpp: In function ‘void solve()’: main.cpp:40:14: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions] 40 | auto [v, cnt] = que.front(); que.pop(); | ^
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<ll, ll>; #define all(a) (a).begin(), (a).end() #define pb push_back #define fi first #define se second mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count()); const ll MOD1000000007 = 1000000007; const ll MOD998244353 = 998244353; const ll MOD[3] = {999727999, 1070777777, 1000000007}; const ll LINF = 1LL << 60LL; const int IINF = (1 << 30) - 1; void solve(){ int N, M; cin >> N >> M; vector<vector<int>> G(N); for(int i=0; i<M; i++){ int u, v; cin >> u >> v; u--; v--; G[u].push_back(v); G[v].push_back(u); } vector<bool> check(N, false); int K; cin >> K; for(int i=0; i<K; i++){ int a; cin >> a; check[a-1] = true; } vector<vector<int>> dist(N, vector<int>(5, -1)); queue<pair<int, int>> que; dist[0][0] = 0; que.push({0, 0}); while(!que.empty()){ auto [v, cnt] = que.front(); que.pop(); for(int to : G[v]){ if(check[to]){ if(cnt < 4){ if(dist[to][cnt+1] != -1) continue; dist[to][cnt+1] = dist[v][cnt] + 1; que.push({to, cnt+1}); } }else{ if(dist[to][0] != -1) continue; dist[to][0] = dist[v][cnt] + 1; que.push({to, 0}); } } } int ans = IINF; for(int i=0; i<5; i++){ if(dist[N-1][i] != -1) ans = min(ans, dist[N-1][i]); } if(ans == IINF) cout << -1 << "\n"; else cout << ans << endl; } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int T=1; //cin >> T; while(T--) solve(); }