글 읽기 - 틀렸습니다) C언어 1753번 최단 경로 다익스트라 질문

hayman42 6년 전 0

C언어 인접리스트를 이용하여 구현하고 몇가지 테스트케이스를 통과해서 제출을 했는데 몇프로 가지도 못하고 틀렸습니다가 뜨네요 ㅠㅠ

너무 코드가 길어 다 보여드리긴 미안해서 다익스트라 함수만 올렸는데 이것도 길긴 하네요 ㅠㅠ

출발 도착이 같은 간선이 여러개인 경우에도 통과하고 출발과 도착이 같은 경우 예외처리도 했는데 어떤 문제가 있는지 알기 힘드네요.

인접리스트하고 main 함수엔 딱히 문제가 없다고 생각해서 올리지 않았는데 혹시 시간이 많으신 착하신 분이 제 다익스트라 함수엔 문제가 없다고 판단하셨다면 채점 번호 7519309번(https://www.acmicpc.net/source...) 을 봐주셨으면 좋겠습니다.

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

typedef unsigned short int itemtype;
typedef struct list *List;
typedef struct wgraph *wGraph;
typedef struct list
{
	itemtype num;        //도착 vertex 의 번호
	itemtype weight;        //가중치
	List aList;
}list;
typedef struct wgraph
{
	itemtype num;        //총 vertex 의 개수
	List *vertex;        //vertex 배열
}wgraph;

void getdis(itemtype start, wGraph G, int *res)
{
	List temp = G->vertex[start]->aList;
	if (!temp)
		return;
	int *dis = (int *)malloc((G->num + 1) * sizeof(int));        //최단 거리
	itemtype *pred = (itemtype *)calloc((G->num + 1), sizeof(itemtype));        //이전 vertex, 이 값이 0인 경우 한 번도 탐색이 되지 않은 vertex
	itemtype *heap = (itemtype *)malloc((G->num + 1) * sizeof(itemtype));
	itemtype rear = 0, i, parent, child, min, cur_pos = start;
	bool *check= (bool *)calloc((G->num + 1), sizeof(bool));        //1인 경우 이미 결정된 vertex

	dis[start] = 0;
	check[start]++;

	while (temp && !check[temp->num])
	{
		while (temp)
		{
			if (!check[temp->num] && (!pred[temp->num] || dis[temp->num] > dis[cur_pos] + temp->weight))
			{    //이미 결정되었거나 이미 탐색했는데 원래 거리가 현재 거리보다 작으면 if 문을 통과 못함
				dis[temp->num] = dis[cur_pos] + temp->weight;
				pred[temp->num] = cur_pos;

				i = ++rear;

				while (i / 2 > 0 && dis[heap[i / 2]] > dis[temp->num])        //heap
				{
					heap[i] = heap[i / 2];
					i /= 2;
				}

				heap[i] = temp->num;
			}

			temp = temp->aList;
		}
		
		parent = 1, child = 2;
		i = rear--;
		min = heap[1];

		while (child <= rear)        //heap sort
		{
			if (child + 1 <= rear && dis[heap[child]] > dis[heap[child + 1]])
				child++;
			if (dis[heap[i]] <= dis[heap[child]])
				break;

			heap[parent] = heap[child];
			parent = child;
			child *= 2;
		}

		heap[parent] = heap[i];

		res[min] = dis[min];        //main 함수에 있는 배열에 거리 입력
		check[min]++;
		cur_pos = min;
		temp = G->vertex[min]->aList;
		min = 0;
	}

	free(dis);
	free(pred);
	free(check);
	free(heap);
	return;
}

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

문제

문제

출처

ICPC

틀렸습니다) C언어 1753번 최단 경로 다익스트라 질문

hayman42 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말