結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 13:50:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 125 ms / 2,000 ms |
コード長 | 1,277 bytes |
コンパイル時間 | 2,163 ms |
コンパイル使用メモリ | 206,780 KB |
実行使用メモリ | 11,808 KB |
最終ジャッジ日時 | 2025-09-06 13:50:46 |
合計ジャッジ時間 | 5,860 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ int n,m; cin >> n >> m; vector<vector<int>>path (n,vector<int>(0)); for(int i=0;i<m;i++){ int x,y; cin >> x >> y; x--,y--; path[x].push_back(y); path[y].push_back(x); } vector<int>iwi (n,0); int k; cin >> k; for(int i=0;i<k;i++){ int x; cin >> x; iwi[x-1] = 1; } int inf = (1<<30); vector<vector<int>>dp (5,vector<int>(n,inf)); dp[0][0] = 0; queue<pair<int,pair<int,int>>>que; que.push({0,{0,0}}); while(!que.empty()){ auto [stp,hoge] = que.front(); auto [app,pos] = hoge; que.pop(); if(stp > dp[app][pos]) continue; for(auto nex:path[pos]){ int np; if(iwi[nex] == 0) np = 0; else np = app + 1; if(np == 5) continue; if(dp[np][nex] > dp[app][pos] + 1){ dp[np][nex] = dp[app][pos] + 1; que.push({dp[np][nex],{np,nex}}); } } } int cnt = inf; for(int i=0;i<5;i++){ cnt = min(cnt,dp[i][n-1]); } if(cnt == inf) cout << "-1" << endl; else cout << cnt << endl; }