글 읽기 - 최단경로 30%에서 자꾸 틀려요ㅠㅠ혹시 뭐 놓친부분 있을까요? (C)

moonhee118 5년 전 1

c++안배워서 C로 구현했습니다..아직 넘넘 부족해요..ㅠㅠ

혹시 몰라서 힙 크기는 최대 vertex 크기보다 2배로 했구요 (이렇게 안해도 될까요??)

힙에서 꺼내고 새로 넣을 때 따로 우선순위(가중치) 변경 안하고 visited 안된건 다 넣어버린다음에 visited 확인만하고 꺼내고 있습니다

(혹시 이 과정에서 뭔가 문제가 있는걸까요..ㅠㅠ??)

그리고 distance 배열에다가 바뀐 가중치 바뀌어야할 때 마다 바꿔서 추후에 프린트하는 형식으로 했습니다..

게시판에 있는 예시는 다 맞는 것 같은데 뭐가 부족한지 모르겠어요ㅠㅠ코드가 넘 더러워서 죄송합니다...제발 도와주세요ㅠㅠ

#include <stdio.h>
#include <malloc.h>
#define INF 987654321
#define MAX_VER 20001
#define MAX_HEAP 40001
#define TRUE 1
#define FALSE 0
int visited[MAX_VER];

typedef struct element {
	int v;
	int u;
	int weight;
	struct element*link;
}element;

element* adj_list[MAX_VER];
void init_adj() { //adj list 초기화
	for (int i = 1; i < MAX_VER; i++)
		adj_list[i] = NULL;
}
void insert_edge(int u, int v, int weight) { //엣지추가
	element* new = (element*)malloc(sizeof(element));
	new->u = u;
	new->v = v;
	new->weight = weight;
	new->link = adj_list[u];
	adj_list[u] = new;
}

typedef struct heapNode {
	int weight; //우선순위 키
	int u;
	int v;
}heapNode;

typedef struct heapType
{
	heapNode heap[MAX_HEAP];
	int heap_size;
}heapType;

void init_heap(heapType*h) {
	h->heap_size = 0;
}

void insert_heap(heapType*h, heapNode new) {
	int i = ++h->heap_size;
	while (i != 1 && h->heap[i / 2].weight > new.weight) {
		h->heap[i] = h->heap[i / 2];
		i = i / 2;
	}
	h->heap[i] = new;
}

heapNode extract_min(heapType*h) {
	heapNode removed = h->heap[1];
	heapNode tmp = h->heap[h->heap_size--];
	int child = 2, parent = 1;
	while (child <= h->heap_size) {
		if (child<h->heap_size && h->heap[child].weight>h->heap[child + 1].weight) child++;
		if (h->heap[child].weight > tmp.weight) break;
		h->heap[parent] = h->heap[child];
		parent = child;
		child = child * 2;
	}
	h->heap[parent] = tmp;
	return removed;
}
heapNode get_min(heapType*h, int v) { //힙에서 가장 작은값 출력
	int i = 0;
	heapNode min;
	while (1) {
		min = extract_min(h);
		if (h->heap_size <= 0) break;
		if (visited[min.v] == FALSE) { //방문되지 않았을경우에만 
			                           //이미 방문되었다면 출력ㄴ
			return min;
		}
		i++;
	}
	min.v = min.weight = min.u = INF; //만약 힙 다 돌렸는데도 못찾았다면 끝
	return min;
}    





int distance[MAX_VER];
void dijkstra_shrotest_path(int s,int v) //스타트정점
{
	int i;
	heapType h; init_heap(&h);
	heapNode tmp_head;
	element* tmp = adj_list[s];
	for (i = 1;i <= v;i++) { //distance 초기화
		distance[i] = INF;
	}
	while (tmp) {
		tmp_head.u = tmp->u;
		tmp_head.v = tmp->v;
		tmp_head.weight = tmp->weight;
		insert_heap(&h, tmp_head); 
		if (distance[tmp->v] > tmp->weight)
			distance[tmp->v] = tmp->weight;
		tmp = tmp->link;
	}
	distance[s] = 0;
	heapNode min;
	heapNode relaxing;
	element* tmp_next;
	visited[s] = TRUE;
	for(i = 1; i <= v; i++) {
		min = get_min(&h, v);
		if (min.v == INF) break; //더이상 노드 없다는 뜻
		visited[min.v] = TRUE; //visited 체크해주고
		for (tmp_next= adj_list[min.v];tmp_next;tmp_next = tmp_next->link) {
			if (!visited[tmp_next->v]) { //아직 visited되지 않았다면
				if (distance[tmp_next->v] > tmp_next->weight + min.weight) {
					distance[tmp_next->v] = tmp_next->weight + min.weight;
				}
				relaxing.u = min.u;
				relaxing.v = tmp_next->v;
				relaxing.weight = min.weight + tmp_next->weight;
				insert_heap(&h, relaxing);
			}
		}
	}
	for (i = 1; i <= v;i++) {
		if (distance[i] == INF) //INF가 아니면 weight 출력
			printf("INF\n");
		else //INF면 INF출력
			printf("%d\n", distance[i]);
	}
}
int main(void) {
	int v, e; //정점개수, 간선개수
	int s, i;//시작정점
	init_adj();
	scanf("%d %d", &v, &e);
	fflush(stdin);
	scanf(" %d", &s);
	int u, ve, w;
	for (i = 0;i < e;i++) {
		scanf("%d %d %d", &u, &ve, &w);
		insert_edge(u, ve, w);	}
	dijkstra_shrotest_path(s, v);
}

moonhee118 5년 전 0

힙 크기를 간선크기로 바꿔주니 되었습니다.

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

문제

문제

출처

ICPC

최단경로 30%에서 자꾸 틀려요ㅠㅠ혹시 뭐 놓친부분 있을까요? (C)

moonhee118 5년 전 1

moonhee118 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말