提出 #38874322

---

ソースコード 拡げる

#include <stdio.h>
#include <stdlib.h>
 
int ec[114514], *es[114514];
 
void ae(int f, int t) {
	es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
	if (es[f] == NULL) exit(2);
	es[f][ec[f]++] = t;
}
 
int from[114514];
 
int q[114514];
 
int main(void) {
	int N, M;
	int i;
	int qs, qe;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	for (i = 0; i < M; i++) {
		int A, B;
		if (scanf("%d%d", &A, &B) != 2) return 1;
		ae(A, B);
		ae(B, A);
	}
	from[N] = N;
	q[0] = N;
	qs = 0;
	qe = 1;
	while (qs < qe) {
		int c = q[qs++];
		for (i = 0; i < ec[c]; i++) {
			int next = es[c][i];
			if (from[next] == 0) {
				from[next] = c;
				q[qe++] = next;
			}
		}
	}
	putchar('1');
	do {
		i = from[i];
		printf(" %d", i);
	} while (i != N);
	putchar('\n');
	return 0;
}

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

int ec[114514], *es[114514];

void ae(int f, int t) {
	es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
	if (es[f] == NULL) exit(2);
	es[f][ec[f]++] = t;
}

int from[114514];

int q[114514];

int main(void) {
	int N, M;
	int i;
	int qs, qe;
	if (scanf("%d%d", &N, &M) != 2) return 1;
	for (i = 0; i < M; i++) {
		int A, B;
		if (scanf("%d%d", &A, &B) != 2) return 1;
		ae(A, B);
		ae(B, A);
	}
	from[N] = N;
	q[0] = N;
	qs = 0;
	qe = 1;
	while (qs < qe) {
		int c = q[qs++];
		for (i = 0; i < ec[c]; i++) {
			int next = es[c][i];
			if (from[next] == 0) {
				from[next] = c;
				q[qe++] = next;
			}
		}
	}
	putchar('1');
	do {
		i = from[i];
		printf(" %d", i);
	} while (i != N);
	putchar('\n');
	return 0;
}

提出情報

ジャッジ結果