Submission #72593680

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int n, m;
int x[128], y[128];
int douro[128][128];
int mincost[128][128];
struct status_s {
  int cur, from, cost;
};
int qs;
struct status_s q[128 * 128 * 128];
void qadjust(int pos) {
  for (;;) {
    int i, mc = pos;
    for (i = 1; i <= 2; i++) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

int n, m;
int x[128], y[128];
int douro[128][128];

int mincost[128][128];

struct status_s {
	int cur, from, cost;
};

int qs;
struct status_s q[128 * 128 * 128];

void qadjust(int pos) {
	for (;;) {
		int i, mc = pos;
		for (i = 1; i <= 2; i++) {
			int c = pos * 2 + i;
			if (c < qs && q[c].cost < q[mc].cost) mc = c;
		}
		if (mc == pos) {
			if (pos == 0) return;
			pos = (pos - 1) / 2;
		} else {
			struct status_s temp = q[pos];
			q[pos] = q[mc];
			q[mc] = temp;
			pos = mc;
		}
	}
}

void qadd(struct status_s s) {
	if (qs + 1 >= (int)(sizeof(q) / sizeof(*q))) {
		puts("OVERFLOW!!!!!");
		exit(42);
	}
	q[qs++] = s;
	qadjust(qs - 1);
}

struct status_s qget(void) {
	struct status_s res = q[0];
	if (qs <= 0) {
		puts("UNDERFLOW!!!!!");
		exit(72);
	}
	if (--qs > 0) {
		q[0] = q[qs];
		qadjust(0);
	}
	return res;
}

int main(void) {
	int i;
	int ans = -1;
	if (scanf("%d%d", &n, &m) != 2) return 1;
	for (i = 1; i <= n; i++) {
		if (scanf("%d%d", &x[i], &y[i]) != 2) return 1;
	}
	memset(douro, -1, sizeof(douro));
	for (i = 0; i < m; i++) {
		int a, b, c;
		if (scanf("%d%d%d", &a, &b, &c) != 3) return 1;
		if (douro[a][b] < 0 || c < douro[a][b]) douro[a][b] = douro[b][a] = c;
	}
	memset(mincost, -1, sizeof(mincost));
	mincost[1][1] = 0;
	qadd((struct status_s){ 1, 1, 0 });
	while (qs > 0) {
		struct status_s cur = qget();
		if (mincost[cur.cur][cur.from] == cur.cost) {
			for (i = 1; i <= n; i++) {
				if (douro[cur.cur][i] >= 0) {
					/* 今の料金所から来た方向と行く方向の内積を取り、それが0以下ならおｋ */
					int cx = x[cur.cur], cy = y[cur.cur];
					int px = x[cur.from], py = y[cur.from];
					int nx = x[i], ny = y[i];
					int dx1 = px - cx, dy1 = py - cy;
					int dx2 = nx - cx, dy2 = ny - cy;
					if (dx1 * dx2 + dy1 * dy2 <= 0) {
						int nc = cur.cost + douro[cur.cur][i];
						if (mincost[i][cur.cur] < 0 || nc < mincost[i][cur.cur]) {
							mincost[i][cur.cur] = nc;
							qadd((struct status_s){ i, cur.cur, nc });
						}
					}
				}
			}
		}
	}
	for (i = 1; i <= n; i++) {
		int c = mincost[2][i];
		if (c >= 0 && (ans < 0 || c < ans)) ans = c;
	}
	printf("%d\n", ans);
	return 0;
}

Submission Info

Judge Result