結果

問題 No.3291 K-step Navigation
ユーザー pengin_2000
提出日時 2025-10-03 22:52:02
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 493 ms / 3,000 ms
コード長 1,831 bytes
コンパイル時間 1,043 ms
コンパイル使用メモリ 28,468 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-10-03 23:31:20
合計ジャッジ時間 4,724 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 51
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:8:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
    8 |         scanf("%lld %lld %lld", &n, &m, &k);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.c:10:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   10 |         scanf("%lld %lld", &s, &t);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~
main.c:16:17: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   16 |                 scanf("%lld %lld", &u[i], &v[i]);
      |                 ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include<stdio.h>
long long int u[4003], v[4003];
long long int dist[2003][2];
long long int q[4003], left, right;
int main()
{
	long long int n, m, k;
	scanf("%lld %lld %lld", &n, &m, &k);
	long long int s, t;
	scanf("%lld %lld", &s, &t);
	s--;
	t--;
	long long int i, j, l;
	for (i = 0; i < m; i++)
	{
		scanf("%lld %lld", &u[i], &v[i]);
		u[i + m] = --v[i];
		v[i + m] = --u[i];
	}
	m *= 2;
	if (k % 2 > 0)
	{
		printf("Yes\n");
		return 0;
	}
	long long int cnt = 0;
	for (i = 0; i < m; i++)
	{
		if (u[i] == s && v[i] != t)
			cnt++;
		if (u[i] == t && v[i] != s)
			cnt++;
	}
	if (cnt > 0)
	{
		printf("Yes\n");
		return 0;
	}
	cnt = 0;
	for (i = 0; i < m; i++)
		if (u[i] == s && v[i] == t)
			cnt++;
	if (cnt == 0)
	{
		printf("No\n");
		return 0;
	}
	for (i = 0; i < m - 1; i++)
	{
		if (u[i] > u[i + 1])
		{
			u[i] ^= u[i + 1];
			u[i + 1] ^= u[i];
			u[i] ^= u[i + 1];
			v[i] ^= v[i + 1];
			v[i + 1] ^= v[i];
			v[i] ^= v[i + 1];
			if (i > 0)
				i -= 2;
		}
	}
	u[n] = -1;
	long long int min, mid, max;
	long long int min_odd_cycle = 2e18;
	for (l = 0; l < n; l++)
	{
		for (i = 0; i < n; i++)
			dist[i][0] = dist[i][1] = 1e18;
		dist[l][0] = 0;
		q[0] = 2 * l;
		left = 0;
		right = 1;
		while (left < right)
		{
			i = q[left];
			left++;
			j = i % 2;
			i /= 2;
			min = -1;
			max = m;
			while (max - min > 1)
			{
				mid = (max + min) / 2;
				if (u[mid] < i)
					min = mid;
				else
					max = mid;
			}
			for (; u[max] == i; max++)
			{
				if (dist[v[max]][1 - j] > dist[i][j] + 1)
				{
					dist[v[max]][1 - j] = dist[i][j] + 1;
					q[right] = 2 * v[max] + 1 - j;
					right++;
				}
			}
		}
		for (i = 0; i < n; i++)
			if (min_odd_cycle > dist[i][0] + dist[i][1])
				min_odd_cycle = dist[i][0] + dist[i][1];
	}
	if (min_odd_cycle + 3 > k)
		printf("No\n");
	else
		printf("Yes\n");
	return 0;
}
0