結果

問題 No.3291 K-step Navigation
ユーザー 00 Sakuda
提出日時 2025-10-03 22:14:02
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,657 bytes
コンパイル時間 1,413 ms
コンパイル使用メモリ 137,088 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-03 22:14:05
合計ジャッジ時間 3,688 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 42 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <queue>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <iomanip>
#include <numeric>
using namespace std;
using ll = long long;
using pp = pair<int, int>;
using vp = vector<pp>;
void BFS(vector<vector<vp>> G, vector<vector<int>> & dist, int s, int p) {
	queue<pp> que;
	que.push({s, p});
	dist[s][p] = 0;
	while (!que.empty()) {
		int v = que.front().first;
		int p = que.front().second;
		que.pop();
		for (auto nv : G[v][p]) {
			int x = nv.first;int np = nv.second;
			if (dist[x][np] == -1) {
				dist[x][np] = dist[v][p] + 1;
				que.push({x, np});
			}
		}
	}

}
int main() {
	int N, M;ll K;int S, T;
	cin >> N >> M >> K >> S >> T;
	S--;T--;
	vector<vector<vp>> G(N, vector<vp>(2));
	vector<vector<bool>> A(N, vector<bool>(N, false));
	for (int i = 0;i < M;i++) {
		int u, v;cin >> u >> v;
		u--;v--;
		A[u][v] = true;
		A[v][u] = true;
		for (int a = 0;a < 2;a++) {
			G[u][a].push_back({v, (a+1)%2});
			G[v][a].push_back({u, (a+1)%2});
		}
	}
	vector<vector<int>> dist1(N, vector<int>(2, -1));
	auto dist2 = dist1;
	auto dist3 = dist1;
	BFS(G, dist1, S, 0);
	BFS(G, dist2, T, 0);
	ll P = K%2;
	if (dist1[T][P] != -1 and dist1[T][P] <= K) {
		cout <<"Yes" << endl;
		return 0;
	}
	for (int a = 0;a < N;a++) for (int b = 0;b < N;b++) {
		if (A[a][b]) continue;
		if (a == b) continue;
		for (int i = 0;i < 2;i++) for (int j = 0;j < 2;j++) {
			// a to b
			if (dist1[a][i] != -1 and dist2[b][j] != -1) {
				ll nd = dist1[a][i] + dist2[b][j] + 1;
				ll NP = (i + j + 1) % 2;
				if (NP == P and nd <= K) {
					cout <<"Yes" << endl;
					return 0;
				}
			}
		}
	}
	cout <<"No" << endl;
}
0