結果

問題 No.3291 K-step Navigation
ユーザー tnakao0123
提出日時 2025-10-05 15:36:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,727 bytes
コンパイル時間 543 ms
コンパイル使用メモリ 63,552 KB
実行使用メモリ 7,816 KB
最終ジャッジ日時 2025-10-05 15:36:52
合計ジャッジ時間 2,423 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 42 WA * 9
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:54:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   54 |   scanf("%d%d%lld%d%d", &n, &m, &k, &s, &t);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:58:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   58 |     scanf("%d%d", &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 3291.cc:  No.3291 K-step Navigation - yukicoder
 */

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

/* constant */

const int MAX_N = 2000;
const int MAX_N2 = MAX_N * 2;

/* typedef */

using ll = long long;
using vi = vector<int>;
using qi = queue<int>;

/* global variables */

bool es[MAX_N][MAX_N];
vi nbrs[MAX_N];
int sds[MAX_N2], tds[MAX_N2];

/* subroutines */

void bfs(int n, int st, int ds[]) {
  fill(ds, ds + n * 2, -1);
  ds[st << 1] = 0;
  qi q;
  q.push(st << 1);

  while (! q.empty()) {
    int u = q.front(); q.pop();
    int ux = (u >> 1), up = (u & 1);
    int vd = ds[u] + 1;
    for (auto vx: nbrs[ux]) {
      int v = (vx << 1) | (up ^ 1);
      if (ds[v] < 0) ds[v] = vd, q.push(v);
    }
  }
}

/* main */

int main() {
  int n, m, s, t;
  ll k;
  scanf("%d%d%lld%d%d", &n, &m, &k, &s, &t);
  s--, t--;
  for (int i = 0; i < m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    u--, v--;
    es[u][v] = es[v][u] = true;
    nbrs[u].push_back(v);
    nbrs[v].push_back(u);
  }

  bfs(n, s, sds);
  bfs(n, t, tds);

  int kp = (k & 1);
  if (kp) { puts("Yes"); return 0; }
  
  int d0 = sds[(t << 1) | kp];
  if (d0 >= 0 && d0 <= k) {
    puts("Yes");
    return 0;
  }

  for (int ux = 0; ux < n; ux++)
    for (int vx = 0; vx < n; vx++)
      if (ux != vx && ! es[ux][vx])
	for (int up = 0; up < 2; up++)
	  for (int vp = 0; vp < 2; vp++)
	    if ((up ^ vp ^ 1) == kp) {
	      int u = (ux << 1) | up;
	      int v = (vx << 1) | vp;
	      if (sds[u] >= 0 && tds[v] >= 0 &&
		  sds[u] + 1 + tds[v] <= k) {
		puts("Yes");
		//printf(" ux=%d,vx=%d\n", ux + 1, vx + 1);
		return 0;
	      }
	  }

  puts("No");
  return 0;
}
0