글 읽기 - 다익스트라 알고리즘을 이용한 경로의 최소값 구하기 문제 입니다.

choidek 6년 전 0

한 9% 대에서 계속 "틀렸습니다." 라고 출력이 나옵니다.

제가 queue를 이용하지 않은 이유는 어차피 push가 모든 vertex들을 배열에 넣을 때 한번 일어나기 때문입니다.

어떤 점이 잘못된 걸까요?

동일 경로에 비용이 다를 경우도 대비하여 조건문을 삽입했습니다.

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

#pragma warning(disable: 4996)

const int INF = 1000000000;

int c_m[1001][1001];
int dist[1001];
int prev[1001];

int node_array[1001];

void dijkstra(int city_num, int start);
void make_array(int city_num);
int is_empty(void);
void erase(int node, int city_num);
int get_min(int city_num, int start);

int main()
{
	int i, u, v, w;
	int bus, city_num, from, to;
	scanf("%d", &city_num);
	scanf("%d", &bus);

	i = 0;
	while (i < bus)
	{
		scanf("%d %d %d", &u, &v, &w);
		if(c_m[u-1][v-1] > w) c_m[u - 1][v - 1] = w;
		else c_m[u - 1][v - 1] = w;
		i++;
	}

	scanf("%d %d", &from, &to);
	from--; to--;

	dijkstra(city_num, from);
	printf("%d", dist[to]);

	return 0;
}

void make_array(int city_num)
{
	int i;
	for (i = 0; i < city_num+1; i++)
	{
		if (i < city_num) node_array[i] = i;
		else node_array[i] = -1;
	}
}

int is_empty(void)
{
	return node_array[0] == -1;
}


int get_min(int city_num, int start)
{
	int index = start;
	int min = dist[node_array[start]];
	for (int i = 0; i < city_num; i++)
	{
		if (node_array[i] != -1 && min > dist[node_array[i]])
		{
			index = node_array[i];
			min = dist[node_array[i]];
		}
	}
	return index;
}

void erase(int node, int city_num)
{
	int i;
	int index = 0;

	for (i = 0; i < city_num; i++)
	{
		if (node_array[i] == node)
		{
			index = i;
			break;
		}
	}

	for (i = index; i < city_num; i++)
	{
		node_array[i] = node_array[i + 1];
	}
}


void dijkstra(int city_num, int start)
{
	int i;
	int min;
	for (i = 0; i < city_num; i++)
	{
		dist[i] = INF;
		prev[i] = -1;
	}

	dist[start] = 0;
	make_array(city_num);

	while (!is_empty())
	{
		min = get_min(city_num, start);
		for (i = min+1; i < city_num; i++)
		{
			if (c_m[min][i])
			{
				if (dist[i] > dist[min] + c_m[min][i])
				{
					dist[i] = dist[min] + c_m[min][i];
					prev[i] = min;
				}
			}
		}
		erase(min, city_num);
	}

jh05013 6년 전 1

"버스 비용은 0보다 크거나 같고"

그리고 push가 정점마다 한 번씩만 일어나진 않습니다. 다익스트라 알고리즘의 진행 과정을 잘 떠올려 보세요.

choidek 6년 전 0

감사합니다

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

문제

문제

출처

ICPC

다익스트라 알고리즘을 이용한 경로의 최소값 구하기 문제 입니다.

choidek 6년 전 0

jh05013 6년 전 1

choidek 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말