글 읽기 - 다익스트라 알고리즘 관련 질문입니다.

qkqkaqk93 6년 전 0

우선 다익스트라 알고리즘을 보고 따라하면서 문제를 해결하긴 하였습니다. 해결하고 궁금한 것이 떠올라 질문합니다.

1. priority queue에 같은 노드가 다른 값을 가지고 들어갈 수 있지 않나요? 원래 다익스트라 알고리즘 자체가 그런건가요?

2. 해당 코드에서 불필요하거나 줄이거나 더 이쁘게 바꿀 수 있는 부분이 있을지 궁금합니다.

코드에 대한 크리틱 부탁드립니다. 모두 감사합니다!

#include <iostream>
#include <queue>
#include <functional>
#include <utility>

#define INF 1e9
using namespace std;

int main()
{
	int v, e, k;
	vector< vector <pair<int, int> > > vec;
	cin >> v >> e>>k;

	vec.resize(v+1);
	for (int i = 0; i < e; i++)
	{
		int u, v, w;
		cin >> u >> v >> w;
		vec[u].push_back(make_pair( v, w ));
	}

	vector<int> nodeValue(v+1,INF);

	priority_queue<pair<int,int>, std::vector<pair<int,int> >, greater<pair<int, int> > > q;
	nodeValue[k] = 0;
	q.push(make_pair(nodeValue[k],k));
	q.push(make_pair(1, 1));

	while (!q.empty())
	{
		int curIdx = q.top().second;
		q.pop();

		for (int j = 0; j < vec[curIdx].size(); j++)
		{
			int to = vec[curIdx][j].first;
			int cost = nodeValue[curIdx] + vec[curIdx][j].second;
			if (nodeValue[to] > cost)
			{
				nodeValue[to] = cost;
				q.push(make_pair(nodeValue[to], to));
			}
		}
	}

	for (int i = 1; i <= v; i++)
	{
		if (nodeValue[i] == INF)
		{
			cout << "INF" << endl;
		}
		else
		{
			cout << nodeValue[i] << endl;
		}
	}
	return 0;
}

sgchoi5 6년 전 0

다른 분이 작성한 더 효율적인 코드를 한 번 보시는게 ... 더 좋으실 듯 하네요 ...

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

문제

문제

출처

ICPC

다익스트라 알고리즘 관련 질문입니다.

qkqkaqk93 6년 전 0

sgchoi5 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말