득이공간
[백준 C++] 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. 우선순위큐를 오름차순으로 정렬하도록 선언합니다.
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 13549 숨바꼭질 3 - 다익스트라 (0) | 2024.01.31 |
---|---|
[백준 C++] 1916 최소비용 구하기 - 다익스트라 (0) | 2024.01.31 |
[백준 C++] 14501 퇴사 - 브루트포스 (1) | 2024.01.30 |
[백준 C++] 1654 랜선 자르기 - 이분탐색 (1) | 2024.01.29 |
[백준 C++] 2805 나무 자르기 - 이분탐색 (0) | 2024.01.29 |