結果
問題 |
No.3263 違法な散歩道
|
ユーザー |
![]() |
提出日時 | 2025-08-18 12:13:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 139 ms / 2,000 ms |
コード長 | 652 bytes |
コンパイル時間 | 2,163 ms |
コンパイル使用メモリ | 206,996 KB |
実行使用メモリ | 15,104 KB |
最終ジャッジ日時 | 2025-08-18 12:13:11 |
合計ジャッジ時間 | 7,446 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main(){ int n,m; cin >> n >> m; vector<vector<int>> G(n); for (int i(0),a,b;i < m;++i){ cin >> a >> b; --a,--b; G[a].emplace_back(b),G[b].emplace_back(a); } int q; cin >> q; vector<int> A(n); for (int i(0),k;i < q;++i) (cin>>k),A[k-1] = 1; vector dist(n,vector<int>(5,1e9)); queue<pair<int,int>> que; dist[0][0] = 0,que.emplace(0,0); while(!que.empty()){ auto [a,b] = que.front(); que.pop(); for (int c:G[a]) if ((b+1)*A[c]<5&&dist[a][b]+1<dist[c][(b+1)*A[c]]){ dist[c][(b+1)*A[c]] = dist[a][b]+1,que.emplace(c,(b+1)*A[c]); } } cout << (dist[n-1][0]==1e9?-1:dist[n-1][0]) << endl; }