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

1753번: 최단경로

cpp

#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. 우선순위큐를 오름차순으로 정렬하도록 선언합니다.