글 읽기 - 다익스트라 런타임 에러

alsidnf 4년 전 0

도와주세요 ㅠㅠ 다익스트라 알고리즘 이용해서 푸는데 런타임 에러를 못찾겠어요ㅠㅠ

chk배열은 chk[위치][가진돈]으로 확인했고 만약 chk 되있지않으면 힙에 넣는 방식으로 했습니다

#include <cstdio>
int T, N, M, K, top, num[101];
bool chk[101][10001];
//티켓노드
struct ticket {
	int u,v;
	int c;
	int d;
}t[10000];
//다익스트라
struct di {
	int now;
	int cost;
	int val;
}d[1000000];

//퀵정렬 
void quick(int left, int right)
{
	int l, r, m;
	ticket temp;
	if (left < right)
	{
		l = left - 1; r = right + 1; m = t[(l + r) / 2].u;
		while (1)
		{
			while (t[++l].u < m);
			while (t[--r].u > m);
			if (l >= r) break;
			temp = t[l]; t[l] = t[r]; t[r] = temp;
		}
		quick(left, l - 1);
		quick(r + 1, right);
	}
}
//위상정렬 up down
void up(int n)
{
	di temp;
	if (n < 2) return;
	if (d[n].val < d[n / 2].val)
	{
		temp = d[n];
		d[n] = d[n / 2];
		d[n / 2] = temp;
		up(n / 2);
	}
}

void down(int n)
{
	int s=n;
	di temp;
	if (n * 2 <= top && d[s].val > d[n * 2].val) s = n * 2;
	if (n * 2 + 1 <= top && d[s].val > d[n * 2 + 1].val) s = n * 2 + 1;
	if (s != n)
	{
		temp = d[s];
		d[s] = d[n];
		d[n] = temp;
		down(s);
	}
}
//초기화 + 입력 + 정렬
void init()
{
	scanf("%d %d %d", &N, &M, &K);

	for (int i = 1; i <= N; i++) num[i] = 0;
	for (int i = 1; i <= N; i++) for(int j=0;j<=M;j++) chk[i][j] = 0;
	top = 0;

	for (int i = 0; i < K; i++) {
		scanf("%d%d%d%d", &t[i].u, &t[i].v, &t[i].c, &t[i].d);
		num[t[i].u]++;
	}
	quick(0, K - 1);
	for (int i = 1; i <= N; i++) num[i] += num[i - 1];
}
int main()
{
	scanf("%d", &T);
	while (T--)
	{
		init();
		di n;//현재 위치
		d[++top].now = 1;
		d[top].cost = M;
		d[top].val = 0;
		while (top)
		{
			n = d[1];
			d[1] = d[top--];
			down(1);
			if (n.now == N)//현재가 N(도착지)이면 브레이크
			{
				printf("%d\n", n.val);
				N = -1;
				break;
			}
			if (chk[n.now][n.cost]) continue;
			chk[n.now][n.cost] = 1;
			for (int i = num[n.now - 1]; i < num[n.now]; i++)
			{
				if (n.cost - t[i].c >= 0 && !chk[t[i].v][n.cost - t[i].c])
				{
					d[++top].now = t[i].v;
					d[top].cost = n.cost - t[i].c;
					d[top].val = n.val + t[i].d;
					up(top);
				}
			}
		}
		if (N != -1) printf("Poor KCM\n");
	}
}

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

문제

문제

출처

ICPC

다익스트라 런타임 에러

alsidnf 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말