글 읽기 - 런타임 에러 원인좀 찾아주세요..

soloranker66 4년 전 0

예시는 나오는데..

런타임에러가 어디서 발생하는지 잘 모르겠어요

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

typedef struct _edge {
	int to, cost;
}_edge;
typedef struct _node {
	int link, size;
	int *edge;
}_node;

int Heap[1001] = { 0, };
int distance[1001], visit[1001] = { 0, }, Eoh = 0;
void Push(int edge), Pop(), relocate(int cur), vectorFull(int temp), swap(int a, int b);
_node *v;
_edge *e;

int main() {
	int size, esize, INF = 1000000000;
	scanf("%d %d", &size, &esize);

	v = malloc(sizeof(_node)*(size + 1));
	e = malloc(sizeof(_edge)*esize);

	for (int i = 1; i <= size; i++) {
		v[i].link = 0;
		v[i].size = 3;
		v[i].edge = malloc(sizeof(int) * 3);
		distance[i] = INF;
	}
	for(int i=0;i<esize;i++){
		int from, to, cost;
		scanf("%d %d %d", &from, &to, &cost);
		e[i].to = to, e[i].cost = cost;

		v[from].edge[v[from].link++] = i;
		if (v[from].link == v[from].size)
			vectorFull(from);
	}
	int start, end;
	scanf("%d %d", &start, &end);

	distance[start] = 0;
	for (int i = 0; i < v[start].link; i++) {
		int next = e[v[start].edge[i]].to;
		if (distance[next] > distance[start] + e[v[start].edge[i]].cost) {
			distance[next] = distance[start] + e[v[start].edge[i]].cost;
			Push(v[start].edge[i]);
		}
	}
	while (Eoh) {
		int pos = e[Heap[1]].to;
		Pop();
		if (visit[pos] == 1) continue;

		visit[pos] = 1;

		for (int i = 0; i < v[pos].link; i++) {
			int next = e[v[pos].edge[i]].to;
			if (distance[next] > distance[pos] + e[v[pos].edge[i]].cost) {
				distance[next] = distance[pos] + e[v[pos].edge[i]].cost;
				Push(v[pos].edge[i]);
			}
		}
	}
	//for (int i = 1; i <= size; i++)
	//	printf("[%d]", distance[i]);
	printf("\n%d", distance[end]);
}
void swap(int a, int b) {
	int temp = Heap[a];
	Heap[a] = Heap[b];
	Heap[b] = temp;
}
void relocate(int cur) {
	int left = cur * 2, right = cur * 2 + 1;
	int min = cur;
	if (left <= Eoh && e[Heap[left]].cost < e[Heap[min]].cost)
		min = left;
	if (right <= Eoh && e[Heap[right]].cost < e[Heap[min]].cost)
		min = right;
	if (cur == min)
		return;
	swap(cur, min);
	relocate(min);
}
void Push(int edge) {
	Eoh += 1;
	Heap[Eoh] = edge;
	int cur = Eoh;
	while (cur > 1 && e[Heap[cur / 2]].cost > e[Heap[cur]].cost) {
		relocate(cur / 2);
		cur /= 2;
	}
}
void Pop() {
	if (Eoh > 0) {
		Heap[1] = Heap[Eoh];
		Heap[Eoh] = 0;
		Eoh -= 1;
		relocate(1);
	}
}
void vectorFull(int temp) {
	v[temp].edge = realloc(v[temp].edge, sizeof(int)*(v[temp].size * 2));
	v[temp].size *= 2;
}

soloranker66 4년 전 0

아 Heap에 간선을 저장해야해서 Heap의 크기가 문제였네요.

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

문제

문제

출처

ICPC

런타임 에러 원인좀 찾아주세요..

soloranker66 4년 전 0

soloranker66 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말