Submission #64236802

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>
#include <inttypes.h>
int ec[412345];
struct edge_s {
  int to, cost;
} *es[412345];
void ae(int from, int to, int cost) {
  es[from] = realloc(es[from], sizeof(*es[from]) * (ec[from] + 1));
  if (es[from] == NULL) exit(2);
  es[from][ec[from]++] = (struct edge_s){ to, cost };
}
struct q_s {
  int64_t cost;
  int node;
};
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

int ec[412345];

struct edge_s {
	int to, cost;
} *es[412345];

void ae(int from, int to, int cost) {
	es[from] = realloc(es[from], sizeof(*es[from]) * (ec[from] + 1));
	if (es[from] == NULL) exit(2);
	es[from][ec[from]++] = (struct edge_s){ to, cost };
}

struct q_s {
	int64_t cost;
	int node;
};

int qsize = 0, qcap = 0;
struct q_s* q;

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

void qadd(int64_t cost, int node) {
	if (qsize >= qcap) {
		qcap = qsize + 1;
		q = realloc(q, sizeof(*q) * qcap);
		if (q == NULL) exit(2);
	}
	q[qsize++] = (struct q_s){ cost, node };
	qadjust(qsize - 1);
}

struct q_s qget(void) {
	struct q_s res;
	if (qsize <= 0) exit(42);
	res = q[0];
	if (--qsize > 0) {
		q[0] = q[qsize];
		qadjust(0);
	}
	return res;
}

int64_t mincost[412345];

int main(void) {
	int N, M, X;
	int i;
	if (scanf("%d%d%d", &N, &M, &X) != 3) return 1;
	for (i = 0; i < M; i++) {
		int u, v;
		if (scanf("%d%d", &u, &v) != 2) return 1;
		ae(u, v, 1);
		ae(N + v, N + u, 1);
	}
	for (i = 1; i < N; i++) {
		ae(i, N + i, X);
		ae(N + i, i, X);
	}
	ae(N + N, N, 0);
	memset(mincost, -1, sizeof(mincost));
	mincost[1] = 0;
	qadd(0, 1);
	while (qsize > 0) {
		struct q_s cur = qget();
		if (mincost[cur.node] == cur.cost) {
			for (i = 0; i < ec[cur.node]; i++) {
				int nn = es[cur.node][i].to;
				int64_t nc = mincost[cur.node] + es[cur.node][i].cost;
				if (mincost[nn] < 0 || nc < mincost[nn]) {
					mincost[nn] = nc;
					qadd(nc, nn);
				}
			}
		}
	}
	printf("%" PRId64 "\n", mincost[N]);
	return 0;
}

Submission Info

Judge Result