글 읽기 - 최단거리 (다익스트라 알고리즘) 질문이요 ㅠㅠ봐주세요

sukwoo0711 7년 전 0

알고리즘은 이렇게짰어요..

시작점을 우선순위 큐에 삽입한 뒤, 큐가 빌때까지 WHILE진행합니다.

큐에서 나온 순서는 COST가 작은 순서이므로

CHECK[코스트가 작은 정점] = TRUE로 바꾸고,

선택된 정점과 인접한 정점의 DIST를 갱신했어요..(나보다 클경우, 나와 똑같이)

7퍼센트 정도에서 틀리는데.. 무슨 예외 있나요?? 배열도 넉넉히줬는데 세상에나 ㅠㅠㅠㅠ

#include <iostream>
#include <queue>
#include <cstdio>
#include <functional>
#include <vector>
#include <memory.h>
#define MAX 30000
#define INF 99999999
using namespace std;
struct vertex {
	int to;
	int cost;
	vertex(int a, int b) : to(a), cost(b) {};
};
typedef pair<int, int> P;
priority_queue<P, vector<P>, greater<P>> pq;
int dist[30000];
int trace[30000] = { -1 };
int check[30000];
vector <vertex> arr[30000];
void diak(int start)
{
	int step = 0;
	for (int i = 0; i < MAX; i++)
		dist[i] = 99999999;
	dist[start] = 0;
	pq.push(make_pair(0,start));
	while (!pq.empty())
	{
		//type : (cost_p, to_p);
		int to_p = pq.top().second;
		int cost_p = pq.top().first;
		pq.pop();
		check[to_p] = 1;	//거리비용이 적은 정점 -> 방문
		for (int i = 0; i < arr[to_p].size(); i++)
		{
			vertex & next = arr[to_p][i];
			//1.선택된 정점을 기준으로 거리정보를 업데이트
			if(dist[next.to] > dist[to_p] + next.cost)
				dist[next.to] = dist[to_p] + next.cost;
			//2.인접한 노드가 있고, 방문을 하지 않은상태라면, 우선순위 큐에 집어넣음
			if(check[next.to] == false)
				pq.push(make_pair(next.cost, next.to));    //COST를 앞에 넣어서 GREATER비교
		}
	}
}
int main()
{
	int start, n, m;
	scanf("%d %d", &n, &m);
	scanf("%d", &start);
	for (int i = 0; i < m; i++)
	{
		int u, v, w;
		scanf("%d %d %d", &u, &v, &w);
		arr[u].push_back(vertex(v, w));
	}
	diak(start);
	for (int i = 1; i <= n; i++)
	{
		if (dist[i] == INF)
			puts("INF");
		else
		{
			printf("%d\n", dist[i]);
		}
	}
}

pichulia 7년 전 0

우선순위 큐에 이상한걸 넣고계시네요.

여기 정답이 안나오는 데이터입니다.

그리고 배열을 넉넉하게 잡으셨어도 우선순위 큐에 너무 많은걸 넣고계신거같네요..

특정 데이터에서는 메모리가 폭발할거 같습니다

6 6
1
1 2 3
2 3 3
3 4 3
4 6 1
1 5 4
5 4 4

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

문제

문제

출처

ICPC

최단거리 (다익스트라 알고리즘) 질문이요 ㅠㅠ봐주세요

sukwoo0711 7년 전 0

pichulia 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말