結果

問題 No.3263 違法な散歩道
コンテスト
ユーザー yuu_w
提出日時 2025-09-06 18:02:21
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 140 ms / 2,000 ms
コード長 1,433 bytes
コンパイル時間 3,225 ms
コンパイル使用メモリ 288,724 KB
実行使用メモリ 14,720 KB
最終ジャッジ日時 2025-09-06 18:02:29
合計ジャッジ時間 7,027 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#define debug(x) cerr << #x << " = " << (x) << "\n"
#else
#define debug(x) void(0)
#endif

typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
	for (int i = 0; i < (int)v.size(); i++)
		os << v[i] << (i + 1 == (int)v.size() ? "" : " ");
	return os;
}

template <typename T>
istream &operator>>(istream &is, vector<T> &v)
{
	for (int i = 0; i < (int)v.size(); i++)
		is >> v[i];
	return is;
}

////////////////////////////////////////////////////////////

int main()
{
	int N, M;
	cin >> N >> M;
	vector<vector<int>> G(N);
	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);
	}
	vector<bool> exist(N, false);
	int K;
	cin >> K;
	for (int i = 0; i < K; i++)
	{
		int A;
		cin >> A;
		exist[A - 1] = true;
	}
	vector dist(N, vector<int>(5, 1e9));
	queue<Pii> Q;
	Q.push({0, 0});
	dist[0][0] = 0;
	while (!Q.empty())
	{
		auto [now, val] = Q.front();
		Q.pop();
		for (auto to : G[now])
		{
			int nval = exist[to] ? val + 1 : 0;
			if (nval > 4 || dist[to][nval] != (int)1e9)
				continue;
			dist[to][nval] = dist[now][val] + 1;
			Q.push({to, nval});
		}
	}
	int ans = *min_element(dist[N - 1].begin(), dist[N - 1].end());
	cout << (ans == (int)1e9 ? -1 : ans) << "\n";
	return 0;
}
0