글 읽기 - 런타임 에러입니다..한번만 봐주십쇼!!

whoareyou 4년 전 0

일단 최소 힙과 인접 리스트로 구현하였습니다. 제가 처음 구현한 알고리즘은 방문한 점이라도 거리를 최소화되는 경우가 되면 힙에 넣어주었습니다. 근데 런타임 에러가 뜨자 insert를 해주어서 pop하는데 오래 걸려서 런타임 에러가 뜨는 줄 알고 insert를 아직 방문하지 않은 정점만 넣어주었습니다. 해당 줄에 주석처리 했음을 볼 수 있습니다.

	#include<stdio.h>
	#include<string.h>
	int V, E,K,end=0;
	int distance[20002] = { 0, };
	typedef struct EDGE {
		struct EDGE*link;
		int weight;
		int connect;
	}EDGE;
	typedef struct Vertex{
		EDGE*link;
	}Vertex;
	typedef struct HEAP {
		int desti;
		int weight;
	}HEAP;
	HEAP heap[30002];
	Vertex vertex[20002] = { 0, };
	void insert(int desti, int w);
	int* pop();
	void new_Edge(int sourc, int desti, int w);
	int main(void)
	{
		int i;
		int source, desti, w;
		int (*temp);
		EDGE*temp_edge;
		temp = (int*)malloc(sizeof(int) * 2);
		scanf("%d %d", &V, &E);
		scanf("%d", &K);//Ks는 출발점
		K--;
		for (i = 0; i < E; i++)
		{
			scanf("%d %d %d", &source, &desti, &w);
			new_Edge(source-1, desti-1, w);
		}
		for (temp_edge = vertex[K].link; temp_edge != NULL; temp_edge = temp_edge->link)
		{
			distance[temp_edge->connect] = temp_edge->weight;
			insert(temp_edge->connect, temp_edge->weight);
		}
		int here,cost;
		while (end!=0)
		{
			temp = pop();//temp[0]가 desti, temp[1]가 temp[0]까지의 최단 거리이다.
			//결국 temp[0]가 now이다.우리는 temp[0]을 방문할 것이다.
			here = temp[0], cost = temp[1];
			if ((temp[1] > distance[temp[0]])&&(distance[temp[0]]!=0)) continue;//이부분에서 temp[1]은 우리가 기존에 저장한 temp[0]까지의 최단 거리이다.
			for(temp_edge=vertex[temp[0]].link;temp_edge!=NULL;temp_edge=temp_edge->link)
			{
			
					if (distance[temp_edge->connect] == 0)//한번도 방문하지 않은 이라면
					{
						distance[temp_edge->connect] = temp[1] + temp_edge->weight;
						insert(temp_edge->connect, distance[temp_edge->connect]);
					}
					else//distance가 0이 아니라면 즉 방문한 적이 있다면 기존에 저장된 점보다 작아야 
					{
						if (distance[temp_edge->connect] > temp[1] + temp_edge->weight)
						{
							distance[temp_edge->connect] = temp[1] + temp_edge->weight;
						//	insert(temp_edge->connect, distance[temp_edge->connect]);
						}
					}
			}	
		}
		for (i = 0; i < V; i++)
		{
			if (i == K)
				printf("%d\n", 0);
			else
			{
				if (distance[i] != 0)
					printf("%d\n", distance[i]);
				else
					printf("INF\n");
			}
		}
	}
	void new_Edge(int sourc, int desti, int w)
	{
		EDGE *new_edge = malloc(sizeof(EDGE));
		EDGE *temp;
		new_edge->link = NULL;
		new_edge->weight = w;
		new_edge->connect = desti;
		if (vertex[sourc].link == NULL)
			vertex[sourc].link = new_edge;
		else
		{
			for (temp = vertex[sourc].link; temp->link != NULL; temp = temp->link);
			temp->link = new_edge;
		}
	}
	void insert(int desti,int w)//큐에 넣을때 시작점부터 해당 점까지의 거리를 넣어ㅇ야한다.사실 이렇다고 해서 딱히 heap을 구현하는 데에는 큰 차이가 생기지 않는다.
	{
		int temp;
		int tempvertex, tempweight;
		heap[end].desti = desti;
		heap[end].weight = w;
		temp = end++;
		while (1)
		{
			if (temp <= 0 || heap[(temp - 1 / 2)].weight <= heap[temp].weight)
				break;
			else
			{
				tempvertex = heap[temp].desti;
				tempweight = heap[temp].weight;
				heap[temp].desti = heap[(temp - 1) / 2].desti;
				heap[temp].weight = heap[(temp - 1) / 2].weight;
				heap[(temp - 1) / 2].desti = tempvertex;
				heap[(temp - 1) / 2].weight = tempweight;
			}
			temp = (temp - 1) / 2;
		}
	
	}
	int* pop()
	{
		int temp[2];
		temp[0]=heap[0].desti, temp[1]=heap[0].weight;
		int left, right;
		end--;
		heap[0].weight = heap[end].weight,heap[0].desti=heap[end].desti;
		int here = 0,next,temp1,temp3;
		while (1)
		{
			left = 2 * here + 1, right = 2 * here + 2;
			if (left >= end)
				break;
			next = here;
			if (heap[next].weight > heap[left].weight)
				next = left;
			if (right<end&&heap[next].weight>heap[right].weight)
				next = right;
			if (next == here)break;
			temp1 = heap[next].desti;
			temp3 = heap[next].weight;
			heap[next].desti = heap[here].desti;
			heap[next].weight = heap[here].weight;
			heap[here].desti = temp1;
			heap[here].weight = temp3;
			here = next;
		}
		return temp;
	}

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

문제

문제

출처

ICPC

런타임 에러입니다..한번만 봐주십쇼!!

whoareyou 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말