結果

問題 No.788 トラックの移動
コンテスト
ユーザー bal4u
提出日時 2019-08-03 12:37:11
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 284 ms / 2,000 ms
コード長 2,593 bytes
コンパイル時間 478 ms
コンパイル使用メモリ 32,128 KB
実行使用メモリ 17,536 KB
最終ジャッジ日時 2024-12-15 07:05:51
合計ジャッジ時間 2,473 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.788 トラックの移動
// 2019.8.3 bal4u

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

typedef long long ll;

#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif

int in() {   // 非負整数の入力
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}

#define QMAX 150000
typedef struct { int t, s; } QUE;
QUE que[QMAX]; int qsize;

#define PARENT(i) ((i)>>1)
#define LEFT(i)   ((i)<<1)
#define RIGHT(i)  (((i)<<1)+1)

void min_heapify(int i) {
	int l, r, min;
	l = LEFT(i), r = RIGHT(i);
	if (l < qsize && que[l].t < que[i].t) min = l; else min = i;
	if (r < qsize && que[r].t < que[min].t) min = r;
	if (min != i) {
		QUE qt = que[i]; que[i] = que[min], que[min] = qt;
		min_heapify(min);
	}
}

void deq() {
	que[0] = que[--qsize];
	min_heapify(0);
}

void enq(int s, int t) {
	int i, min;
	i = qsize++;
	que[i].s = s, que[i].t = t;
	while (i > 0 && que[min = PARENT(i)].t > que[i].t) {
		QUE qt = que[i]; que[i] = que[min], que[min] = qt;
		i = min;
	}
}

#define Inf 0x7fffffffffffffffLL
#define inf 0x77777777
int N, M, L;
int t[2002];
int dis[2002][2002];
int hi[2002], *to[2002], *len[2002];

void dijkstra(int start, int *dis) {
	int i, s, e, d, nd;

	dis[start] = 0, qsize = 0, enq(start, 0);
	while (qsize) {
		s = que[0].s, d = que[0].t, deq();
		if (dis[s] < d) continue;
		;
		for (i = 0; i < hi[s]; i++) {
			e = to[s][i], nd = d + len[s][i];
			if (dis[e] > nd) dis[e] = nd, enq(e, nd);
		}
	}
}

int main()
{
	int i, j, a, b, c; ll s, ans;
	int *memo, sz;

	N = in(), M = in(), L = in() - 1;
	sz = 0; for (i = 0; i < N; i++) sz += t[i] = in();
	if (sz == 1) { puts("0"); return 0; }

	memo = malloc(3 * sizeof(int)*M);
	sz = 0; for (i = 0; i < M; i++) {
		memo[sz++] = a = in() - 1, memo[sz++] = b = in() - 1, memo[sz++] = in();
		hi[a]++, hi[b]++;
	}
	for (i = 0; i < N; i++) if (hi[i]) {
		to[i] = malloc(hi[i] * sizeof(int));
		len[i] = malloc(hi[i] * sizeof(int));
	}
	memset(hi, 0, sizeof(int)*N);
	i = 0; while (i < sz) {
		a = memo[i++], b = memo[i++], c = memo[i++];
		j = hi[a]++, to[a][j] = b, len[a][j] = c;
		j = hi[b]++, to[b][j] = a, len[b][j] = c;
	}
	free(memo);

	memset(dis, inf, sizeof(dis));
	for (i = 0; i < N; i++)	dijkstra(i, dis[i]);

	ans = Inf;
	for (i = 0; i < N; i++) {
		s = 0, b = -inf;
		for (j = 0; j < N; j++) if (t[j]) {
			s += ((ll)dis[i][j] << 1) * t[j];
			a = dis[i][j] - dis[L][j];
			if (a > b) b = a;
		}
		s -= b;
//		printf("[%d] b=%d, s=%lld, ans=%lld\n", i, b, s, ans);
		if (s < ans) ans = s;
	}
	printf("%lld\n", ans);
	return 0;
}
0