글 읽기 - 1753) C언어 2~4%에서 시간초과가 나오는데 이유를 잘 모르겠습니다...

vect_r 2년 전 0

어느 부분에서 시간초과가 나는 건지를 잘 모르겠습니다.

2~4%에서 틀린 것이니 무한 루프가 걸린 것 같기도 한데, 어디가 문제인지를 도무지 모르겠습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <math.h>

typedef struct node {
	int nodeNum;
	int weight;
	struct node* next;
} Node;

typedef struct {
	int nodeNum;
	double weight;
} PQNode;

typedef struct {
	PQNode data[300003];
	int numOfData;
} PQ;

int V = 0, E = 0, startIdx = 0;
Node* input[20002] = { 0 };// dummyNode사용
PQ pq;

double Distance[20002] = { 0 };

void PQInit();
void PQPush(int nodeNum, double weight);
PQNode PQPop();

void Dijkstra();

Node* makeNode(int nodeNum, int weight);
void pushNode(int startNode, int endNode, int weight);

int main(void) {
	int A = 0, B = 0, C = 0;
	(void)scanf("%d %d", &V, &E);
	(void)scanf("%d", &startIdx);

	for (int i = 1; i <= V; i++)
		input[i] = makeNode(-1, -1);

	for (int i = 0; i < E; i++) {
		(void)scanf("%d %d %d", &A, &B, &C);
		pushNode(A, B, C);
	}

	Dijkstra();

	for (int i = 1; i <= V; i++)
		if (Distance[i] >= INFINITY - 100.0) printf("INF\n");
		else printf("%lld\n", (int64_t)Distance[i]);
	return 0;
}

void Dijkstra() {
	for (int i = 1; i <= V; i++)// Distance 초기화
		Distance[i] = INFINITY;
	Distance[startIdx] = 0;

	PQNode current;
	Node* next;
	PQInit();
	PQPush(startIdx, 0);
	while (1) {
		current = PQPop();

		if (current.nodeNum == -1) break;
		else if (Distance[current.nodeNum] < current.weight) continue;
		
		next = input[current.nodeNum];
		Distance[current.nodeNum] = current.weight;

		while (1) {
			next = next->next;
			if (next == NULL) break;
			else if (Distance[next->nodeNum] > current.weight + next->weight) {
				Distance[next->nodeNum] = current.weight + next->weight;
				PQPush(next->nodeNum, Distance[next->nodeNum]);
			}
		}
	}
}

void PQInit() {
	pq.numOfData = 0;
}

void PQPush(int nodeNum, double weight) {
	pq.data[++pq.numOfData] = (PQNode){ nodeNum, weight };
	int p = 0, c = pq.numOfData;
	PQNode temp;
	while (1) {
		p = c / 2;
		if (p == 0) break;
		else if (pq.data[p].weight > pq.data[c].weight) {
			temp = pq.data[p];
			pq.data[p] = pq.data[c];
			pq.data[c] = temp;
		}
		else break;
		c = p;
	}
}

PQNode PQPop() {
	if (pq.numOfData == 0) return (PQNode) { -1, -1 };
	PQNode retVal = pq.data[1], temp;
	pq.data[1] = pq.data[pq.numOfData--];
	int parent = 1, child = 2;
	while (child <= pq.numOfData) {
		if (child < pq.numOfData && pq.data[child].weight > pq.data[child + 1].weight) child++;
		if (pq.data[child].weight > pq.data[parent].weight) break;
		temp = pq.data[child];
		pq.data[child] = pq.data[parent];
		pq.data[parent] = temp;
		child *= 2;
	}
	return retVal;
}

Node* makeNode(int nodeNum, int weight) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->next = NULL;
	newNode->nodeNum = nodeNum;
	newNode->weight = weight;
	return newNode;
}

void pushNode(int startNode, int endNode, int weight) {
	Node* newNode = makeNode(endNode, weight);
	newNode->next = input[startNode]->next;
	input[startNode]->next = newNode;
}

seico75 2년 전 0

80줄에 등호를 넣으면 어떨까요?

같은 경우 무한하게 넣다 뺐다 할 것 같아요

vect_r 2년 전 0

line 80: else if (Distance[next->nodeNum] >= current.weight + next->weight) {

위와 같이 등호를 추가해도 시간초과가 나오네요...

vect_r 2년 전 0

PQPop()의 line: 120 전에 parent = child; 해주는 것을 빼먹었네요...

수정된 버전은 아래에 두겠습니다. (동적 할당, 고정 길이 배열)

// 동적 할당
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <math.h>

typedef struct node {
	int nodeNum;
	int weight;
	struct node* next;
} Node;

typedef struct {
	int nodeNum;
	double weight;
} PQNode;

typedef struct {
	PQNode data[300003];
	int numOfData;
} PQ;

int V = 0, E = 0, startIdx = 0;
Node* input[20002] = { 0 };// dummyNode사용
PQ pq;

double Distance[20002] = { 0 };

void PQInit();
void PQPush(int nodeNum, double weight);
PQNode PQPop();

void Dijkstra();

Node* makeNode(int nodeNum, int weight);
void pushNode(int startNode, int endNode, int weight);

int main(void) {
	int A = 0, B = 0, C = 0;
	(void)scanf("%d %d", &V, &E);
	(void)scanf("%d", &startIdx);

	for (int i = 1; i <= V; i++)
		input[i] = makeNode(-1, -1);

	for (int i = 0; i < E; i++) {
		(void)scanf("%d %d %d", &A, &B, &C);
		pushNode(A, B, C);
	}

	Dijkstra();

	for (int i = 1; i <= V; i++)
		if (Distance[i] >= INFINITY - 100.0) printf("INF\n");
		else printf("%lld\n", (int64_t)Distance[i]);
	return 0;
}

void Dijkstra() {
	for (int i = 1; i <= V; i++)// Distance 초기화
		Distance[i] = INFINITY;
	Distance[startIdx] = 0;

	PQNode current;
	Node* next;
	PQInit();
	PQPush(startIdx, 0);
	while (1) {
		current = PQPop();

		if (current.nodeNum == -1) break;
		else if (Distance[current.nodeNum] < current.weight) continue;

		next = input[current.nodeNum];
		Distance[current.nodeNum] = current.weight;

		while (1) {
			next = next->next;
			if (next == NULL) break;
			else if (Distance[next->nodeNum] > current.weight + next->weight) {
				Distance[next->nodeNum] = current.weight + next->weight;
				PQPush(next->nodeNum, Distance[next->nodeNum]);
			}
		}
	}
}

void PQInit() {
	pq.numOfData = 0;
}

void PQPush(int nodeNum, double weight) {
	pq.data[++pq.numOfData] = (PQNode){ nodeNum, weight };
	int p = 0, c = pq.numOfData;
	PQNode temp;
	while (1) {
		p = c / 2;
		if (p == 0) break;
		else if (pq.data[p].weight > pq.data[c].weight) {
			temp = pq.data[p];
			pq.data[p] = pq.data[c];
			pq.data[c] = temp;
		}
		else break;
		c = p;
	}
}

PQNode PQPop() {
	if (pq.numOfData == 0) return (PQNode) { -1, -1 };
	PQNode retVal = pq.data[1], temp;
	pq.data[1] = pq.data[pq.numOfData--];
	int parent = 1, child = 2;
	while (child <= pq.numOfData) {
		if (child < pq.numOfData && pq.data[child].weight > pq.data[child + 1].weight) child++;
		if (pq.data[child].weight > pq.data[parent].weight) break;
		temp = pq.data[child];
		pq.data[child] = pq.data[parent];
		pq.data[parent] = temp;
		parent = child;
		child *= 2;
	}
	return retVal;
}

Node* makeNode(int nodeNum, int weight) {
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->next = NULL;
	newNode->nodeNum = nodeNum;
	newNode->weight = weight;
	return newNode;
}

void pushNode(int startNode, int endNode, int weight) {
	Node* newNode = makeNode(endNode, weight);
	newNode->next = input[startNode]->next;
	input[startNode]->next = newNode;
}



// 고정 길이 배열
#define _CRT_SECURE_NO_WARNINGS
#define MAXNode 20005
#define MAXEdge 300005
#define INF 1000000000
#include <stdio.h>

typedef struct {
	int startNode;
	int endNode;
	int weight;
	int link;// 배열로 연결 리스트를 구성하는 용도
} Edge;

typedef struct {
	int nodeNum;
	int weight;
} Heap;

int V = 0, E = 0, startIdx = 0;
Edge edge[MAXEdge] = { 0 };// 간선 받고, 이 자체로 연결 리스트를 생성

int pointEdge[MAXNode] = { 0 };// 배열(edge)로 연결 리스트 생성하기 위한 임시 저장소
int distance[MAXNode] = { 0 };// 누적(and 최종) 결과 저장용

int heapNumber = 0;// 힙의 크기
Heap heap[MAXEdge];// 힙 (간선의 개수보다 약간 크게 지정)

void swap(Heap* h1, Heap* h2);// 두 힙_노드를 swap
void HPush(Heap h);// 힙에 노드 추가
Heap HPop();// 힙에서 노드 반환 및 삭제
void Dijkstra(int startIdx);// 주 함수

int main(void) {
	(void)scanf("%d %d %d", &V, &E, &startIdx);
	for (int i = 1; i <= E; i++) {
		(void)scanf("%d %d %d", &edge[i].startNode, &edge[i].endNode, &edge[i].weight);
		edge[i].link = pointEdge[edge[i].startNode];// 초기에 0을 받으면, 무시한다.(0은 사용 안함)
		pointEdge[edge[i].startNode] = i;
	}

	Dijkstra(startIdx);
	for (int i = 1; i <= V; i++)
		if (distance[i] >= INF - 100) printf("INF\n");
		else printf("%d\n", distance[i]);

	return 0;
}

void swap(Heap* h1, Heap* h2) {
	Heap temp = *h1;
	*h1 = *h2;
	*h2 = temp;
}

void HPush(Heap h) {
	heap[++heapNumber] = h;
	int c = heapNumber, p = c / 2;
	while (p != 0) {
		p = c / 2;
		if (heap[p].weight > heap[c].weight) swap(&heap[p], &heap[c]);
		else break;
		c = p;
	}
}

Heap HPop() {
	if (heapNumber == 0) return (Heap) { -1, -1 };
	Heap retVal = heap[1];
	int current = 1, child = 2;
	heap[1] = heap[heapNumber--];
	while (child <= heapNumber) {
		if (child < heapNumber && heap[child].weight > heap[child + 1].weight) child++;
		if (heap[child].weight >= heap[current].weight) break;
		swap(&heap[child], &heap[current]);
		current = child;
		child = current * 2;
	}
	return retVal;
}

void Dijkstra(int startIdx) {
	for (int i = 1; i <= V; i++)
		distance[i] = INF;
	distance[startIdx] = 0;

	Heap temp;
	HPush((Heap) { startIdx, 0 });
	while (heapNumber != 0) {
		temp = HPop();
		if (distance[temp.nodeNum] < temp.weight) continue;
		for (int i = pointEdge[temp.nodeNum]; i != 0; i = edge[i].link) {
			if (distance[edge[i].endNode] > temp.weight + edge[i].weight) {
				distance[edge[i].endNode] = temp.weight + edge[i].weight;
				HPush((Heap) { edge[i].endNode, distance[edge[i].endNode] });
			}
		}
	}
}

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

문제

문제

출처

ICPC

1753) C언어 2~4%에서 시간초과가 나오는데 이유를 잘 모르겠습니다...

vect_r 2년 전 0

seico75 2년 전 0

vect_r 2년 전 0

vect_r 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말