C++ 백준 1916: 최소비용 구하기

 

기본적인 다익스트라 문제이다.

 

> 출발 노드와 도착 노드가 정해지지 않았다.> 도시의 개수 1000, 버스의 개수 100,000 이므로 시간유의

 

큐에 해당 노드가 저장 되어있는 상태에서 그 노드의 최소값이 새롭게 초기화가 되면 이미 큐에 들어있던 노드는 쓸모가 없으므로, 이를 처리하는 것이 포인트인 것 같다.

 

#include <iostream>
#include <queue>
#include <climits>

std::vector<std::vector<std::pair<int, int>>> list;
std::vector<int> ans;

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);

	int n, m;
	std::cin >> n >> m;

	int a, b, c;
	list.assign(n + 1, std::vector<std::pair<int, int>>());
	for (int i{ 0 }; i < m; i++) {
		std::cin >> a >> b >> c;

		list[a].push_back(std::make_pair(c, b));
	}
	int k;
	std::cin >> a >> k;

	std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> q;
	q.push(std::make_pair(0, a));

	ans.assign(n + 1, INT_MAX);
	ans[a] = 0;
	
	while (!q.empty()) {
		a = q.top().first; // 가중치
		b = q.top().second; // 현재 노드번호
		q.pop();

		if (a > ans[b]) continue;

		for (int i{ 0 }; i < list[b].size(); i++) {
			if (ans[b] + list[b][i].first < ans[list[b][i].second]) {
				ans[list[b][i].second] = ans[b] + list[b][i].first;
				q.push(std::make_pair(ans[list[b][i].second], list[b][i].second));
			}
		}
	}

	std::cout << ans[k] << "\n";
}