[백준 C++] 1916 최소비용 구하기 - 다익스트라

1916번: 최소비용 구하기

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

const int& Infinite = INT_MAX;

vector<vector<pair<int, int>>> Neighbors;
vector<int> LinkState;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> SearchQueue;

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

	for (int i = 0; i < InM; ++i)
	{
		int Src, Dst, Cst;
		cin >> Src >> Dst >> Cst;
		Neighbors[Src - 1].emplace_back(Dst - 1, Cst);
	}

	LinkState.reserve(InN);
	for (int i = 0; i < InN; ++i)
	{
		LinkState.emplace_back(Infinite);
	}
}

void Dijkstra(int InStart)
{
	SearchQueue.emplace(0, InStart - 1);

	while (!SearchQueue.empty())
	{
		int Current = SearchQueue.top().second;
		int CurrentCst = SearchQueue.top().first;
		SearchQueue.pop();

		if (CurrentCst > LinkState[Current])
		{
			continue;
		}

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;
	Init(N, M);

	int Start, End;
	cin >> Start >> End;
	LinkState[Start - 1] = 0;

	Dijkstra(Start);

	cout << LinkState[End - 1];
}

---

1753(최단경로) 문제와 같은 유형의 문제입니다.

역시 다익스트라 알고리즘으로 풀었습니다.

 

중요한 부분은 최소비용이 이미 구해진 노드를 우선순위 큐에서 재탐색하게 될 경우에

인접 리스트 탐색 구문을 스킵하도록 해서 시간복잡도를 최소화하는 것입니다.