글 읽기 - 75%에서 시간초과 어느부분 문제일까요

soloranker66 4년 전 0

75%에서 시간초과가 나는데 코드의 어느부분이 문제일까요

https://www.acmicpc.net/problem/1916

이 문제에서는 36ms로 통과했는데 여기선 안먹히는 코드인건가요?

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

typedef struct _edge {
	int to, cost;
}_edge;
typedef struct _node {
	int link, size;
	int *edge;
}_node;

int Heap[300001] = { 0, };
int distance[20001];
int Eoh = 0;
void Push(int edge), Pop(), relocate(int cur), vectorFull(int temp), swap(int a, int b);
_node *v;
_edge *e;

int main() {
	int size, esize, start, INF = 3000001;
	scanf("%d %d %d", &size, &esize, &start);

	v = malloc(sizeof(_node)*(size + 1));
	e = malloc(sizeof(_edge)*esize);

	for (int i = 1; i <= size; i++) {
		v[i].link = 0;
		v[i].size = 100;
		v[i].edge = malloc(sizeof(int) * 100);
		distance[i] = INF;
	}
	for (int i = 0; i < esize; i++) {
		int from, to, cost;
		scanf("%d %d %d", &from, &to, &cost);
		e[i].to = to, e[i].cost = cost;

		v[from].edge[v[from].link++] = i;
		if (v[from].link == v[from].size)
			vectorFull(from);
	}

	distance[start] = 0;
	for (int i = 0; i < v[start].link; i++) {
		int next = e[v[start].edge[i]].to;
		if (distance[next] > distance[start] + e[v[start].edge[i]].cost) {
			distance[next] = distance[start] + e[v[start].edge[i]].cost;
			Push(v[start].edge[i]);
		}
	}
	while (Eoh) {
		int pos = e[Heap[1]].to;
		Pop();
		for (int i = 0; i < v[pos].link; i++) {
			int next = e[v[pos].edge[i]].to;
			if (distance[next] > distance[pos] + e[v[pos].edge[i]].cost) {
				distance[next] = distance[pos] + e[v[pos].edge[i]].cost;
				Push(v[pos].edge[i]);
			}
		}
	}
	for (int i = 1; i <= size; i++)
		if (distance[i] == INF)
			printf("INF\n");
		else
			printf("%d\n", distance[i]);
}
void swap(int a, int b) {
	int temp = Heap[a];
	Heap[a] = Heap[b];
	Heap[b] = temp;
}
void relocate(int cur) {
	int left = cur * 2, right = cur * 2 + 1;
	int min = cur;
	if (left <= Eoh && e[Heap[left]].cost < e[Heap[min]].cost)
		min = left;
	if (right <= Eoh && e[Heap[right]].cost < e[Heap[min]].cost)
		min = right;
	if (cur == min)
		return;
	swap(cur, min);
	relocate(min);
}
void Push(int edge) {
	Eoh += 1;
	Heap[Eoh] = edge;
	int cur = Eoh;
	while (cur > 1 && e[Heap[cur / 2]].cost > e[Heap[cur]].cost) {
		relocate(cur / 2);
		cur /= 2;
	}
}
void Pop() {
	if (Eoh > 0) {
		Heap[1] = Heap[Eoh];
		Heap[Eoh] = 0;
		Eoh -= 1;
		relocate(1);
	}
}
void vectorFull(int temp) {
	v[temp].edge = realloc(v[temp].edge, sizeof(int)*(v[temp].size * 2));
	v[temp].size *= 2;
}

soloranker66 4년 전 0

간선의 가중치를 담는게 아니라 간선을 통해 이동하는 노드의 가중치를 담아놓으니까 해결됬네요..

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

문제

문제

출처

ICPC

75%에서 시간초과 어느부분 문제일까요

soloranker66 4년 전 0

soloranker66 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말