Submission #55749811

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>
#define MAX_N 212345
struct edge_s {
  int to, cost;
};
int ec[MAX_N * 2];
struct edge_s* es[MAX_N * 2];
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]].to = to;
  es[from][ec[from]].cost = cost;
  ec[from]++;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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

#define MAX_N 212345

struct edge_s {
	int to, cost;
};

int ec[MAX_N * 2];
struct edge_s* es[MAX_N * 2];

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]].to = to;
	es[from][ec[from]].cost = cost;
	ec[from]++;
}

int Q_cap = 0, Q_size = 0;
struct q_s {
	int node;
	int64_t cost;
} *Q;

void qadjust(int pos) {
	for (;;) {
		int minpos = pos;
		int i;
		for (i = 1; i <= 2; i++) {
			int c = pos * 2 + i;
			if (c < Q_size && 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[minpos];
			Q[minpos] = Q[pos];
			Q[pos] = temp;
			pos = minpos;
		}
	}
}

void qadd(int node, int64_t cost) {
	if (Q_size >= Q_cap) {
		Q_cap = Q_size + 1;
		Q = realloc(Q, sizeof(*Q) * Q_cap);
		if (Q == NULL) exit(2);
	}
	Q[Q_size].node = node;
	Q[Q_size].cost = cost;
	Q_size++;
	qadjust(Q_size - 1);
}

struct q_s qget(void) {
	struct q_s ret;
	if (Q_size <= 0) exit(99);
	ret = Q[0];
	Q_size--;
	if (Q_size > 0) {
		Q[0] = Q[Q_size];
		qadjust(0);
	}
	return ret;
}

int64_t mincost[MAX_N * 2];

int main(void) {
	int N, M;
	int i;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	Q_cap = N * 2 + M * 2;
	Q = malloc(sizeof(*Q) * Q_cap);
	if (Q == NULL) return 2;
	for (i = 1; i <= N; i++) {
		int A;
		if (scanf("%d", &A) != 1) return 1;
		ae(i, i + MAX_N, A);
	}
	for (i = 0; i < M; i++) {
		int U, V, B;
		if (scanf("%d%d%dd", &U, &V, &B) != 3) return 1;
		ae(U + MAX_N, V, B);
		ae(V + MAX_N, U, B);
	}
	memset(mincost, -1 ,sizeof(mincost));
	mincost[1] = 0;
	qadd(1, 0);
	while (Q_size > 0) {
		struct q_s cur = qget();
		if (cur.cost == mincost[cur.node]) {
			for (i = 0; i < ec[cur.node]; i++) {
				int next_node = es[cur.node][i].to;
				int64_t next_cost = cur.cost + es[cur.node][i].cost;
				if (mincost[next_node] < 0 || mincost[next_node] > next_cost) {
					mincost[next_node] = next_cost;
					qadd(next_node, next_cost);
				}
			}
		}
	}
	printf("%" PRId64, mincost[2 + MAX_N]);
	for (i = 3; i <= N; i++) {
		printf(" %" PRId64, mincost[i + MAX_N]);
	}
	putchar('\n');
	return 0;
}

/*

各頂点を、入口と出口に分ける
入口→出口に、その頂点の重みをコストとする辺を張る

*/

Submission Info

Judge Result