글 읽기 - 66%에서 시간초과가 해결이 안됩니다

junu0124 4년 전 0

1에서 N가는 힙,

N에서 1가는 힙

이렇게 힙을 두번 돌려서 다익스트라를 썼는데, 어디서 시간을 줄여야할지 모르겠습니다 ㅠㅠ

반례도 못찾겠고... 부탁드립니다 ㅠㅠ

#include<stdio.h>
#define maxnum 1e14
int N, M;
long long int D, E;
long long int height[100001];
long long int max=-maxnum;

typedef struct qwe {
	int u, v;
	int g;
}qwe;

typedef struct _heap_data {
	int node; // 노드 번호
	long long int dist; // 우선순위
} heapdata;

heapdata heap[400002], _tmp;
int heap_size;

qwe input[400002];
int list[200002];
int lcnt = 1;
int dnchk[100002];
int upchk[100002];
long long int dndist[100002];
long long int updist[100002];
long long int totaldist[100002];

void swap(qwe* x, qwe* y);
void nrquick_sort(int s, int e);
void swap_heapdata(heapdata* x, heapdata* y);

void heapup(int cur);
void heapdown(int cur);
void push(int node, long long int dist);
void pop();

int main() {
	scanf("%d %d %lld %lld", &N, &M, &D, &E);

	for (int i = 1; i <= N; ++i) {
		scanf("%lld", &height[i]);
	}

	for (int i = 1; i <= M; ++i) {
		scanf("%d %d %lld", &input[i].u, &input[i].v, &input[i].g);
	}
	for (int i = 1; i <= M; ++i) {
		input[M + i] = { input[i].v,input[i].u,input[i].g };
	}

	M *= 2;
	nrquick_sort(1, M);

	input[M + 1].u = N + 1;
	for (int i = 1; i <= M + 1; i++) {
		while (input[i].u >= lcnt) list[lcnt++] = i;
	}

	for (int i = 1; i <= N; i++) {
		dndist[i] = maxnum;
		updist[i] = maxnum;
	}
	
	dndist[N] = 0;
	push(N, 0);

	while (heap_size > 0)
	{
		int cur = heap[1].node;
		pop();

		if (dnchk[cur])
			continue;
		dnchk[cur] = 1;

		for (int k = list[cur]; k < list[cur + 1]; k++)
		{
			int next = input[k].v;
			long long int cost = input[k].g;

			if (height[cur] >= height[input[k].v]) continue;

			if (dndist[next] > dndist[cur] + cost * D)
			{
				dndist[next] = dndist[cur] + cost * D;
				push(next, dndist[next]);
			}
		}
	}

	for (int i = 2; i <= N - 1; ++i) {
		if (dndist[i] == maxnum) continue;
		dndist[i] = height[i] * E - dndist[i];
	}

	updist[1] = 0;
	push(1, 0);

	while (heap_size > 0)
	{
		int cur = heap[1].node;
		pop();

		if (upchk[cur])
			continue;
		upchk[cur] = 1;

		for (int k = list[cur]; k < list[cur + 1]; k++)
		{
			int next = input[k].v;
			long long int cost = input[k].g;

			if (height[cur] >= height[input[k].v]) continue;

			if (updist[next] > updist[cur] + cost * D)
			{
				updist[next] = updist[cur] + cost * D;
				push(next, updist[next]);
			}
		}
	}
	for (int i = 2; i <= N - 1; ++i) {
		if (dndist[i] == maxnum || updist[i] == maxnum) continue;
		totaldist[i] = dndist[i] - updist[i];

		if (max < totaldist[i]) max = totaldist[i];
	}

	if (max == -maxnum) printf("Impossible");
	else printf("%lld", max);

}

void swap(qwe * x, qwe * y) {
	qwe _tmp = *x;
	*x = *y;
	*y = _tmp;
}
void nrquick_sort(int s, int e)
{
	if (s >= e) return;

	int l = s - 1, r = e + 1;
	int pivot = input[(s + e) / 2].u;

	while (1)
	{
		while (input[++l].u < pivot);
		while (input[--r].u > pivot);
		if (l >= r) break;
		swap(&input[l], &input[r]);
	}

	nrquick_sort(s, l - 1);
	nrquick_sort(r + 1, e);
}
void swap_heapdata(heapdata * x, heapdata * y) {
	heapdata _tmp = *x;
	*x = *y;
	*y = _tmp;
}

void heapup(int cur)
{
	// 가중치dist로 비교
	if (cur > 1 && heap[cur].dist < heap[cur / 2].dist)
	{
		swap_heapdata(&heap[cur], &heap[cur / 2]);
		heapup(cur / 2);
	}
}
void heapdown(int cur)
{
	int c1 = 2 * cur, c2 = 2 * cur + 1;
	int min_child = cur;

	if (c1 <= heap_size && heap[c1].dist < heap[min_child].dist) min_child = c1;
	if (c2 <= heap_size && heap[c2].dist < heap[min_child].dist) min_child = c2;

	if (min_child != cur)
	{
		swap_heapdata(&heap[cur], &heap[min_child]);
		heapdown(min_child);
	}
}
void push(int node, long long int dist) {
	heap_size++;
	heap[heap_size].node = node;
	heap[heap_size].dist = dist;
	heapup(heap_size);
}
void pop() {
	swap_heapdata(&heap[1], &heap[heap_size]);
	heap[heap_size] = { 0,0 };
	heap_size--;
	heapdown(1);
}

sait2000 4년 전 1

퀵소트는 최악의 경우 O(n^2)입니다. 표준 라이브러리에 있는 정렬을 써보세요.

junu0124 4년 전 0

감사합니다..

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

문제

문제

출처

ICPC

66%에서 시간초과가 해결이 안됩니다

junu0124 4년 전 0

sait2000 4년 전 1

junu0124 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말