[백준 C++] 1753 최단경로 - 다익스트라

1753번: 최단경로

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

vector<vector<pair<int, int>>> Neighbors;
vector<int> LinkState;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> NonVisited; // 오름차순 PQ

const int& Infinite = INT_MAX;

void Init(int InV, int InE, int InK)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	Neighbors.reserve(InV);
	for (int i = 0; i < InV; ++i)
	{
		Neighbors.emplace_back(vector<pair<int, int>>());
	}

	for (int i = 0; i < InE; ++i)
	{
		int Src, Dest, Weight;
		cin >> Src >> Dest >> Weight;

		Neighbors[Src - 1].emplace_back(Dest - 1, Weight);
	}

	LinkState.reserve(InV);
	for (int i = 0; i < InV; ++i)
	{
		LinkState.emplace_back(Infinite);
	}
	LinkState[InK - 1] = 0;
}

void Dijkstra(int InK)
{
	NonVisited.emplace(0, InK - 1);

	while (!NonVisited.empty())
	{
		// Choose Short Distance Node
		int Current = NonVisited.top().second;
		NonVisited.pop();

		// Update Neighbors LinkState
		for (const pair<int, int>& Neighbor : Neighbors[Current])
		{
			if (LinkState[Current] + Neighbor.second < LinkState[Neighbor.first])
			{
				LinkState[Neighbor.first] = LinkState[Current] + Neighbor.second;
				NonVisited.emplace(LinkState[Neighbor.first], Neighbor.first);
			}
		}
	}
}

int main()
{
	int V, E, K;
	cin >> V >> E >> K;

	Init(V, E, K);

	Dijkstra(K);

	for (const int& Distance : LinkState)
	{
		if (Distance == Infinite)
		{
			cout << "INF" << '\n';
		}
		else
		{
			cout << Distance << '\n';
		}
	}
}

---

 

감격의 첫 골드 문제입니다.

다익스트라 알고리즘을 이용해서 구현했습니다.

 

중요 구현 부분은 다음과 같습니다.

1. 시간복잡도 최소화를 위해서 탐색할 노드를 담을 자료구조로 벡터가 아닌 우선순위큐를 사용합니다.

2. 우선순위큐를 오름차순으로 정렬하도록 선언합니다.