結果

問題 No.3263 違法な散歩道
コンテスト
ユーザー vxxv
提出日時 2025-09-06 14:09:11
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 246 ms / 2,000 ms
コード長 1,194 bytes
コンパイル時間 3,984 ms
コンパイル使用メモリ 291,652 KB
実行使用メモリ 18,560 KB
最終ジャッジ日時 2025-09-06 14:09:21
合計ジャッジ時間 8,698 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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, vector<int>());
    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);
    }
    int K;
    cin >> K;
    set<int> A;
    for (int i = 0; i < K; ++i) {
    	int a;
    	cin >> a;
    	a--;
    	A.insert(a);
    }
    vector<vector<int>> v(N, vector<int>(5, -1));
    queue<tuple<int, int, int>> que;
    que.push({0, 0, 0});
    while (!que.empty()) {
    	tuple<int, int, int> T = que.front();
    	que.pop();
    	if (A.count(get<0>(T))) {
    		get<2>(T)++;
    	} else {
    		get<2>(T) = 0;
    	}
    	if (get<2>(T) == 5) continue;
    	if (v[get<0>(T)][get<2>(T)] != -1) continue;
    	v[get<0>(T)][get<2>(T)] = get<1>(T);
    	for (int i = 0; i < G[get<0>(T)].size(); ++i) {
    		que.push({G[get<0>(T)][i], get<1>(T) + 1, get<2>(T)});
    	}
    }
    int ans = 1000000000;
    for (int i = 0; i < 5; ++i) {
    	if (v[N - 1][i] != -1) {
    		ans = min(ans, v[N - 1][i]);
    	}
    }
    if (ans == 1000000000) {
    	cout << -1 << endl;
    } else {
    	cout << ans << endl;
    }
}
0