글 읽기 - 런타임 에러 (InsufficientSpace)가 발생합니다.

pinoco3 2년 전 0

인접리스트 다익스트라 알고리즘을 공부하고 있습니다.

제목과 같은 런타임 에러가 발생했습니다.

어떤 부분이 잘못됐을까요?

그리고 인접리스트를 공부하기 좋은 문제도 추천해주시면 감사하겠습니다.

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define v_max 20001
#define max 300001
int st_n;
int m_node[v_max]={0,};
bool v_node[v_max]={0,};
typedef struct g_node{
	int ver;
	int data;
	struct g_node* next;
}g_node;
typedef struct g_type{
	g_node* g_list[v_max];
}g_type;
int dij(g_type *g,int start){
	int min=max,i,j,k,temp,l_n=start;
	g_node* now;
	v_node[start]=1;
	now=g->g_list[start];
	while(now!=NULL){		//시작노드 간선 가중치 넣기 
		if(now->ver==start);
		else if(m_node[now->ver]>now->data||(now->ver!=start&&m_node[now->ver]==0)){
			m_node[now->ver]=now->data;
		}
		if(min>m_node[now->ver]){
			min=m_node[now->ver];
			temp=now->ver;
		}
		now=now->next;
	}
	
	while(l_n!=temp){
		l_n=temp;
		v_node[l_n]=1;
		now=g->g_list[l_n];
		min=max;
		while(now!=NULL){
			if(now->ver==start);
			else if(m_node[now->ver]>(now->data+m_node[l_n])||(now->ver!=start&&m_node[now->ver]==0)){
				m_node[now->ver]=now->data+m_node[l_n];
			}
			if(min>m_node[now->ver]){
				min=m_node[now->ver];
				temp=now->ver;
			}
			now=now->next;
		}
	}
	return 0;
}
int add_edge(g_type *g,int ed1,int ed2,int d){
	g_node* n_node;
	n_node=(g_node*)malloc(sizeof(n_node));
	n_node->data=d;
	n_node->ver=ed2;
	n_node->next=g->g_list[ed1];
	g->g_list[ed1]=n_node;
	return 0;
}
int init_g(g_type *g,int node){
	int i;
	for(i=1;i<=node;i++){
		g->g_list[i]=NULL;
	}
	return 0;
}
int main(){
	int v,e,i;
	int e1,e2,d;
	g_type* g;
	g=(g_type*)malloc(sizeof(g));
	scanf("%d %d",&v,&e);
	init_g(g,v);
	scanf("%d",&st_n);
	for(i=0;i<e;i++){
		scanf("%d %d %d",&e1,&e2,&d);
		add_edge(g,e1,e2,d);
	}
	dij(g,st_n);
	for(i=1;i<=v;i++){
		if(m_node[i]==0&&i!=st_n){
			printf("INF\n");
		}
		else{
			printf("%d\n",m_node[i]);
		}
	}
	free(g);
	return 0;
}

delena0702 2년 전 1

55, 73행의 메모리 할당 부분의 크기가 잘못된것 같습니다.

n_node=(g_node*)malloc(sizeof(g_node)); // 55
g=(g_type*)malloc(sizeof(g_type)); // 73

55행 기준 n_node는 g_node* 타입이기 때문에, g_node타입과는 크기가 다릅니다.

pinoco3 2년 전 0

동적할당을 잘 안쓰다보니 이런 실수가 있었나봅니다.

수정하니 런타임에러는 해결 됐습니다. 감사합니다.

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

문제

문제

출처

ICPC

런타임 에러 (InsufficientSpace)가 발생합니다.

pinoco3 2년 전 0

delena0702 2년 전 1

pinoco3 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말