글 읽기 - 지점 간 최소비용 갱신을 안했는데요

lunatic1997 7년 전 0

지점 간 최소비용 갱신을 무시하고 풀어봤는데 패스가 되었습니다 왜 그런건지 궁금하네여

힙 다익스트라로 짰고 갱신작업없이 그냥 inf 배열안에 모든 간선정보를 다 담아서 돌렸습니다

왜 문제가 안되는걸까요??

#include <stdio.h>
long long int N, M, start, end, inf[100010][3], cnt[1010], st = 1, xx[100010][2], djk[1010], chk[1010];

void quick(long long int left, long long int right)
{
	long long int q, r, m, s, t, x;
	if (right > left)
	{
		q = left - 1; r = right + 1;
		m = inf[(left + right) / 2][0];
		while (1)
		{
			while (inf[++q][0] < m);
			while (inf[--r][0] > m);
			if (q >= r) break;
			s = inf[q][0]; inf[q][0] = inf[r][0]; inf[r][0] = s;
			t = inf[q][1]; inf[q][1] = inf[r][1]; inf[r][1] = t;
			x = inf[q][2]; inf[q][2] = inf[r][2];  inf[r][2] = x;
		}
		quick(left, q - 1);
		quick(r + 1, right);
	}
}

void up(long long int a){
	long long int t_1, t_2;

	if (a > 1){
		if (xx[a][1] < xx[a / 2][1]){
			t_1 = xx[a][0], xx[a][0] = xx[a / 2][0], xx[a / 2][0] = t_1;
			t_2 = xx[a][1], xx[a][1] = xx[a / 2][1], xx[a / 2][1] = t_2;
			up(a / 2);
		}
	}
}

void down(long long int b){
	long long int p_1, p_2, max = b, l = b * 2, r = b * 2 + 1;

	if (l < st){
		if (xx[l][1] < xx[max][1]){
			max = l;
		}
	}
	if (r < st){
		if (xx[r][1] < xx[max][1]){
			max = r;
		}
	}

	if (max != b){
		p_1 = xx[max][0], xx[max][0] = xx[b][0], xx[b][0] = p_1;
		p_2 = xx[max][1], xx[max][1] = xx[b][1], xx[b][1] = p_2;
		down(max);
	}
}

void inque(long long int c, long long int d){
	xx[st][0] = c, xx[st][1] = d;
	++st;
}

int main(void)

{
	long long int i, j, k, now, next, cost;

	scanf("%lld", &N);

	for (i = 1; i <= N; ++i){
		djk[i] = 99999999999;
	}

	scanf("%lld", &M);

	for (i = 0; i < M; ++i){
		scanf("%lld %lld %lld", &inf[i][0], &inf[i][1], &inf[i][2]);
		++cnt[inf[i][0]];
	}

	quick(0, M - 1);

	scanf("%lld %lld", &start, &end);

	for (i = 1; i <= N; ++i){
		cnt[i] = cnt[i - 1] + cnt[i];
	}									//간선리스트 작업;

	djk[start] = 0;
	inque(start, 0);

	while (st > 1){

		now = xx[1][0];

		if (chk[now] == 0){
			chk[now] = 1;

			for (i = cnt[now - 1]; i <= cnt[now] - 1; ++i){
				next = inf[i][1];
				cost = inf[i][2];

				if (chk[next] == 0){
					if (djk[next] > djk[now] + cost){
						djk[next] = djk[now] + cost;
						inque(next, djk[next]);
						up(st - 1);
					}
				}
			}
		}

		--st;

		if (st > 1){
			xx[1][0] = xx[st][0], xx[1][1] = xx[st][1];
			down(1);
		}
	}

	printf("%lld", djk[end]);

	return 0;
}

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

문제

문제

출처

ICPC

지점 간 최소비용 갱신을 안했는데요

lunatic1997 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말