結果

問題 No.1 道のショートカット
コンテスト
ユーザー bal4u
提出日時 2019-04-07 15:40:33
言語 C
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 1,874 bytes
コンパイル時間 238 ms
コンパイル使用メモリ 31,360 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-08 05:09:56
合計ジャッジ時間 4,804 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 9 WA * 3 RE * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'in':
main.c:11:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
   11 | #define gc() getchar_unlocked()
      |              ^~~~~~~~~~~~~~~~
main.c:17:24: note: in expansion of macro 'gc'
   17 |         int n = 0, c = gc();
      |                        ^~

ソースコード

diff # 

// yukicoder: No.1 道のショートカット
// 2019.4.7 bal4u
// 最短距離に関する問題。bfsでやってみる

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//// 高速入力
#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif
int in()    // 非負整数の入力
{
	int n = 0, c = gc();
	//	while (isspace(c)) c = gc();
	do n = 10 * n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

#define INF   0x55555555
#define MAXN  55
typedef struct{ int node, money, t; } Q;
Q q[100000]; int top, end;

int C; // 使える金額の上限
int N; // 町数
int V; // 道路の本数
int hi[MAXN], *to[MAXN], *money[MAXN], *tim[MAXN];
int total[MAXN];
int S[MAXN], T[MAXN], Y[MAXN], M[MAXN];

int bfs(int start, int goal)
{
	int i, s, m, t, nxt;

	memset(total, INF, sizeof(total));
	q[0].node = start, q[0].money = 0, q[0].t = 0, end = 1;
	while (top != end) {
		s = q[top].node, m = q[top].money, t = q[top++].t;

		if (t >= total[s]) continue;
		total[s] = t;
		if (s == goal) continue;

		for (i = 0; i < hi[s]; i++) {
			if (m + money[s][i] > C) continue;
			nxt = to[s][i];
			if (t + tim[s][i] < total[nxt]) {
				q[end].node = nxt, q[end].money = m + money[s][i];
				q[end++].t = t + tim[s][i];
			}
		}
	}
	return total[goal] < INF? total[goal]: (-1);
}

int main()
{
	int i, k, s;

	N = in(), C = in(), V = in();
	for (i = 0; i < V; i++) S[i] = in(), hi[S[i]]++;
	for (i = 0; i < V; i++) T[i] = in();
	for (i = 0; i < V; i++) Y[i] = in();
	for (i = 0; i < V; i++) M[i] = in();
	for (i = 1; i <= N; i++) if (hi[i]) {
		to[i] = malloc(sizeof(int)*hi[i]);
		money[i] = malloc(sizeof(int)*hi[i]);
		tim[i] = malloc(sizeof(int)*hi[i]);
	}
	memset(hi, 0, sizeof(hi));
	for (i = 0; i < V; i++) {
		s = S[i];
		k = hi[s]++;
		to[s][k] = T[i], money[s][k] = Y[i], tim[s][k] = M[i];
	}

	printf("%d\n", bfs(1, N));
	return 0;
}
0