[Baekjoon] 1916번: 최소비용 구하기

🥅 문제

https://www.acmicpc.net/problem/1916

 

🔍 설계

인접 리스트를 활용하여 데이크스트라 알고리즘으로 해결할 수 있다.

 

다만, 우선순위 큐를 활용하므로, 이미 어느 정점까지 가는데 최소 비용으로 갱신되었을 수도 있으므로, 확인 후 skip하는 것이 필요하다. 그렇지 않으면 인접한 정점까지 반복문을 또 돌게 되어 시간 초과가 발생한다.

 

👊 풀이

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

int n, m, start, endd, cost, a, b;
vector<vector<pair<int, int>>> adj_list(1001);
vector<int> dist(1001, 1e9 + 7);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

void Dijkstra() {
	dist[a] = 0;
	pq.push({ 0, a });
	while (!pq.empty()) {
		int cur_cost = pq.top().first;
		int cur_node = pq.top().second;
		pq.pop();
		if (cur_cost > dist[cur_node]) {
			continue;
		}
		for (int i = 0; i < adj_list[cur_node].size(); i++) {
			int next_node = adj_list[cur_node][i].second;
			int next_cost = cur_cost + adj_list[cur_node][i].first;
			if (dist[next_node] > next_cost) {
				dist[next_node] = next_cost;
				pq.push({ next_cost, next_node });	
			}
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> start >> endd >> cost;
		adj_list[start].push_back({ cost, endd });
	}
	cin >> a >> b;
	
	Dijkstra();

	cout << dist[b] << "\n";

	return 0;
}