結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
|
提出日時 | 2025-09-06 13:14:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 232 ms / 2,000 ms |
コード長 | 1,439 bytes |
コンパイル時間 | 2,452 ms |
コンパイル使用メモリ | 209,308 KB |
実行使用メモリ | 32,844 KB |
最終ジャッジ日時 | 2025-09-06 13:16:59 |
合計ジャッジ時間 | 6,696 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; vector<int> BFS(vector<vector<int>> &Graph,int start){ int N = Graph.size(); vector<int> ret(N,-1); queue<int> Q; ret.at(start) = 0,Q.push(start); while(Q.size()){ int pos = Q.front(); Q.pop(); for(auto to : Graph.at(pos)){ if(ret.at(to) != -1) continue; ret.at(to) = ret.at(pos)+1; Q.push(to); } } return ret; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N,M; cin >> N >> M; vector<pair<int,int>> UV(M); for(auto &[u,v] : UV) cin >> u >> v,u--,v--; int K; cin >> K; vector<bool> NG(N); while(K--){ int a; cin >> a; NG.at(a-1) = true; } vector<vector<int>> Graph(N*5); for(auto [u,v] : UV){ for(int k=0; k<5; k++){ if(NG.at(v)){ if(k < 4) Graph.at(u+k*N).push_back(v+k*N+N); } else Graph.at(u+k*N).push_back(v); swap(u,v); if(NG.at(v)){ if(k < 4) Graph.at(u+k*N).push_back(v+k*N+N); } else Graph.at(u+k*N).push_back(v); swap(u,v); } } auto dist = BFS(Graph,0); int answer = 1001001001; for(int i=0; i<5; i++){ if(dist.at(N-1+i*N) != -1) answer = min(answer,dist.at(N-1+i*N)); } if(answer > 1e9) answer = -1; cout << answer << endl; }