글 읽기 - 다익스트라의 체크에 관해서

cocobo123 5년 전 0

힙을 이용한 다익스트라를 구현했습니다.

70번 부터 다익스트라 알고리즘입니다.

제가 궁금한 점은 이전에 다익스트라를 적용한 문제에서 똑같이 힙을 이용하여 다익스트라를 구현하고 풀었을 땐 맞았습니다.

하지만 이번에는 계속 틀렸다고 나오네요.

문제가 될 것 같은 check 를 없애면 정답이 나옵니다.

여기서 궁금한게

힙을 이용했을 때 check 를 쓰지 않아도 맞는 이유가 궁금합니다.

또 check를 썼을 때 왜 틀렸는지 잘 모르겠습니다.

u -> v 로 가는 경로가 여러개 있다고 한 들

check[u] = 1 이고 v는 아직 check 되지 않았기에 충분히 갱신될텐데

제가 어느부분을 놓치고 있는지 궁금합니다.

#include<stdio.h>
#define MaxV 20001
#define MaxE 300001
#define INF 0x7fffffff
//1. 리스트만들기
typedef struct node {
	int to;
	int cost;
	struct node * next;
}Node;

Node list[MaxV], dummy[MaxV], mem[MaxE];
int memIdx;

Node * alloc() {
	return &mem[memIdx++];
}

//2. 힙
int heap[MaxE], heapIdx;
int dist[MaxV], check[MaxV];
void insert(int nowN) {
	int nowIdx = ++heapIdx;

	while (nowIdx != 1) {
		int parentIdx = nowIdx / 2;
		if (dist[nowN] < dist[heap[parentIdx]]) {
			heap[nowIdx] = heap[parentIdx];
			nowIdx = parentIdx;
		}
		else
			break;
	}
	heap[nowIdx] = nowN;
	return;
}

int cmpChild(int nowIdx) {
	int Lchild = nowIdx * 2,
		Rchild = nowIdx * 2 + 1;

	if (Lchild > heapIdx)
		return 0;
	else if (Lchild == heapIdx)
		return Lchild;
	else 
		return dist[heap[Lchild]] < dist[heap[Rchild]] ? Lchild : Rchild;
}

int myDelete() {
	int nowIdx = 1,
		childIdx,
		res = heap[nowIdx],
		last = heap[heapIdx--];

	while (childIdx = cmpChild(nowIdx)) {
		if (dist[last] > dist[heap[childIdx]]) {
			heap[nowIdx] = heap[childIdx];
			nowIdx = childIdx;
		}
		else
			break;
	}
	heap[nowIdx] = last;
	return res;
}

//3. 다익스트라
//dist의 초기값은 INF
void dijkstra(int start) {

	dist[start] = 0;
	insert(start);

	while (heapIdx) {
		int from = myDelete();

		if (check[from] == 0) {
			check[from] = 1;

			Node * temp = list[from].next->next;
			while (temp) {
				int to = temp->to,
					cost = temp->cost;
				if (dist[to] > dist[from] + cost) {
					dist[to] = dist[from] + cost;
					insert(to);
					check[to] = 0;
				}
				temp = temp->next;
			}
		}
	}
}

int main() {
	int V, E, K;
	scanf("%d %d %d", &V, &E, &K);
	for (int i = 1; i <= V; i++) {
		dist[i] = INF;
		list[i].to = i;
		list[i].cost = 0;
		list[i].next = &dummy[i];
		dummy[i].to = dummy[i].cost = 0;
		dummy[i].next = NULL;
	}

	while (E--) {
		int from, to, cost;
		scanf("%d %d %d", &from, &to, &cost);

		Node * newNode = alloc();
		newNode->to = to;
		newNode->cost = cost;
		newNode->next = list[from].next->next;
		list[from].next->next = newNode;
	}

	dijkstra(K);

	for (int i = 1; i <= V; i++)
		if (dist[i] == INF)
			printf("INF\n");
		else
			printf("%d\n", dist[i]);
	return 0;
}

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

문제

문제

출처

ICPC

다익스트라의 체크에 관해서

cocobo123 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말