글 읽기 - [틀렸습니다] 코드가 많이 복잡하지만 도와주세요..

answn8376 6년 전 0

틀린 케이스가 어떤게 있는지 잘 모르겠습니다..

코드가 너무 길고 복잡해서 알아보기 힘들겠지만 주석이라도 달아드릴게요!!

죄송합니다 도와주십쇼!

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

#define INF 99999999
#define min(x, y) x < y ? x : y


typedef struct Node* NodePointer;
typedef struct Node {
	int from;
	int to;
	int w;
	NodePointer link;
}Node;

int v, e;
int start;

void append(int, NodePointer);
NodePointer create(int, int, int);
void process();

NodePointer list[22222];
NodePointer tail[22222];

int dist[22222];
int visit[22222];

int heap[2222222];

int last;


void add(int n) {    //힙에 추가하는 부분. 마지막에 추가한 다음 부모와 검사해서 올려보낸다.
	int temp;
	int parent, child;

	heap[++last] = n;

	temp = heap[last];

	child = last;
	parent = child / 2;

	while (parent > 0) {
		if (dist[heap[child]] < dist[heap[parent]]) {    //힙은 dist가 작은 게 위로 간다.
			heap[child] = heap[parent];
			child = parent;
			parent = child / 2;
		}

		else
			break;
	}

	heap[child] = temp;
}

int del() {    //힙에서 뽑아내고 제일 마지막에 있는 놈을 root로 올리고 내려가면서 검사
	int ret;
	int parent, child, temp;

	if (last == 0)
		return -1;

	ret = heap[1];

	temp = heap[last--];
	heap[1] = temp;

	parent = 1;
	child = 2;

	while (child <= last) {

		if (child < last && dist[heap[child + 1]] < dist[heap[child]]) {
			child = child + 1;
		}


		if (dist[heap[child]] < dist[temp]) {    //힙은 dist가 작은 게 위로 간다.
			heap[parent] = heap[child];
			parent = child;
			child = child * 2;
		}

		else
			break;
	}

	heap[parent] = temp;

	return ret;
}

int main(void) {
	int i;
	int from, to, w;
	NodePointer np;

	//freopen("input.txt", "r", stdin); //테스트 케이스 입력

	scanf("%d %d", &v, &e);
	scanf("%d", &start);

	for (i = 1; i <= v; i++) {
		dist[i] = INF;
	}

	dist[start] = 0;

	for (i = 1; i <= e; i++) {        //입력받아 인접리스트로 만든다.
		scanf("%d %d %d", &from, &to, &w);
		np = create(from, to, w);
		append(from, np);
	}

	add(start);    //시작점을 heap에 넣는다.

	process();

	for (i = 1; i <= v; i++) {
		if (dist[i] == INF)
			printf("INF\n");

		else
			printf("%d\n", dist[i]);
	}
}

void process() {
	int j, finished = 0;
	int temp;
	NodePointer np;

	for(j = 0; j < v; j++) {
		
		temp = del();        //힙에서 하나 뽑아온다.

		if (temp < 0) break;    //힙이 비어있으면 -1이 return되서 종료.

		while (visit[temp] != 0) {    //이미 방문한 vertex는 넘어간다.
			temp = del();
			
			if (temp < 0) {
				finished = 1;
				break;
			}
		}

		if (finished)            //힙이 비어있으면 -1이 return되서 종료.
			break;

		visit[temp] = 1;        //방문했다는 걸 표시

		np = list[temp];        //인접리스트의 맨 앞쪽 노드는 np에 저장. (np는 edge정보)

        //while문을 돌면서 가야할 노드가 기존에 가지고 있는 dist보다 여기서 가는게 더 적으면 바꾼다.
        //ex)  현재 np가 1에서 2로 가는 edge이고 w가 3이면 dist[1] + 3 과 dist[2]를 비교해서
        //    더 작은 값을 dist[2]에 저장.
        
		while (np) {            
			dist[np->to] = min(dist[np->to], dist[np->from] + np->w);

			add(np->to);        //힙에 지금 방문한 vertex에서 갈 수 있는 vertex들을 저장.

			np = np->link;
		}
	}
}

void append(int i, NodePointer np) {    //노드들을 인접리스트로 만든다.

	if (list[i] == NULL || tail[i] == NULL) {
		list[i] = np;
		tail[i] = np;
		return;
	}

	tail[i]->link = np;
	tail[i] = np;
}

NodePointer create(int from, int to, int w) {    //인접리스트의 노드 하나를 만든다.
	NodePointer temp;

	temp = (NodePointer)malloc(sizeof(Node));

	temp->from = from;
	temp->to = to;
	temp->w = w;
	temp->link = NULL;

	return temp;
}

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

문제

문제

출처

ICPC

[틀렸습니다] 코드가 많이 복잡하지만 도와주세요..

answn8376 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말