글 읽기 - 두개의 차이로 왜 정답과 틀렸습니다로 갈리는지 모르겠습니다

kdr06006 4년 전 1

위 코드는 정답코드이고 밑에 코드는 틀렸다고 뜨는데 왜 그런건가요??

1번줄은 공통으로 들어가있는 코드입니다.

3~16이 정답코드이고, 18~22는 틀린코드입니다.

다른 코드는 다 똑같습니다.

혹시나 해서 코드 첨부 하겠습니다.

/*inline int min(int a, int b) { return a < b ? a : b; }

int res1 = 0;
	res1 += BFS(1, n1);
	res1 += BFS(n1, n2);
	res1 += BFS(n2, N);

	int res2 = 0;
	res2 += BFS(1, n2);
	res2 += BFS(n2, n1);
	res2 += BFS(n1, N);

	res1 = min(res1, res2);

	if (res1 >= INF) puts("-1");
	else printf("%d\n", res1);

int res1 = min((BFS(1, n1) + BFS(n1, n2) + BFS(n2, N)),
		(BFS(1, n2) + BFS(n2, n1) + BFS(n2, N)));

	if (res1 >= INF) puts("-1");
	else printf("%d\n", res1);

*/

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#define _size 801
#define heap link[0]

typedef struct Queue {
	int cur, num;
}Q;
Q* link[_size];
int size[_size], cap[_size];
bool check[_size];
const int INF = 1e8 + 1;

inline int min(int a, int b) { return a < b ? a : b; }
inline void swap(Q& a, Q& b) { Q temp = a; a = b; b = temp; }

void Re(int idx, Q a)
{
	size[idx]++;
	if (size[idx] >= cap[idx]) {
		Q* T = (Q*)realloc(link[idx], sizeof(Q) * (cap[idx] += 10));
		link[idx] = T;
	}
	link[idx][size[idx] - 1] = a;
}

void up(int idx)
{
	if (idx == 0) return;
	int par = (idx - 1) / 2;
	if (heap[idx].num < heap[par].num) {
		swap(heap[idx], heap[par]);
		up(par);
	}
}

void down(int idx)
{
	int cha = idx, L = idx * 2 + 1, R = idx * 2 + 2;
	if (L<size[0] && heap[cha].num > heap[L].num) cha = L;
	if (R<size[0] && heap[cha].num > heap[R].num) cha = R;
	if (cha != idx) {
		swap(heap[cha], heap[idx]);
		down(cha);
	}
}

void Enqueue(Q a)
{
	Re(0, a);
	up(size[0] - 1);
}

Q Dequeue()
{
	Q tmp = heap[0];
	heap[0] = heap[--size[0]];
	down(0);
	return tmp;
}

int BFS(int start, int finish)
{
	memset(check, 0, sizeof(check));
	size[0] = 0;
	Enqueue({ start,0 });

	while (size[0]) {
		Q Cur = Dequeue();
		if (check[Cur.cur]) continue;
		if (Cur.cur == finish) return Cur.num;
		check[Cur.cur] = 1;

		for (int i = 0; i < size[Cur.cur]; i++) {
			Q Next = link[Cur.cur][i];
			Next.num += Cur.num;
			if (!check[Next.cur]) Enqueue(Next);
		}
	}

	return INF;
}

int main(void)
{
	int N, M, n1, n2, n3;
	scanf("%d %d", &N, &M);
	for (int i = 0; i <= N; i++) link[i] = (Q*)malloc(sizeof(Q));

	while (M--) {
		scanf("%d %d %d", &n1, &n2, &n3);
		Re(n1, { n2,n3 });
		Re(n2, { n1,n3 });
	}

	scanf("%d %d", &n1, &n2);
	int res1 = 0;
	res1 += BFS(1, n1);
	res1 += BFS(n1, n2);
	res1 += BFS(n2, N);

	int res2 = 0;
	res2 += BFS(1, n2);
	res2 += BFS(n2, n1);
	res2 += BFS(n1, N);

	res1 = min(res1, res2);

	if (res1 >= INF) puts("-1");
	else printf("%d\n", res1);

	for (int i = 0; i <= N; i++) free(link[i]);
}

kcm1700 4년 전 1

일단 차이로 보이는 건 실행 순서겠네요.

int res1 = min((BFS(1, n1) + BFS(n1, n2) + BFS(n2, N)),
(BFS(1, n2) + BFS(n2, n1) + BFS(n2, N)));

로 작성하신 라인에서는 BFS가 어떤 순서로 호출되는지 정해진 게 없고 컴파일러 맘일 겁니다.

jangzzang 4년 전 2

건구 ㅎㅇ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

두개의 차이로 왜 정답과 틀렸습니다로 갈리는지 모르겠습니다

kdr06006 4년 전 1

kcm1700 4년 전 1

jangzzang 4년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말