結果

問題 No.3263 違法な散歩道
ユーザー DeltaStruct
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #

#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;
}
0