백준 1916번: 최소비용 구하기

[문제 링크]

1916번: 최소비용 구하기

---

다익스트라 알고리즘을 이용하는 문제였다.

입력으로 주어지는 버스의 정보를 간선으로 연결하고, 출발 도시를 시작 정점으로 하는 다익스트라 알고리즘을 수행하면 출발 도시에서 모든 도시로 가는 최소 비용을 구할 수 있다. 여기서 도착 도시로 가는 최소 비용을 찾아 출력해주면 원하는 결과를 얻을 수 있다.

---

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

const int INF = 987654321;
int N, M;
vector<pair<int, int>> adj[1001];

int dijkstra(int start, int arrive){
	vector<int> dist(N+1, INF);
	dist[start] = 0;
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, start });

	while (!pq.empty()) {
		int here = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();

		if (dist[here] < cost) continue;

		for (int i = 0; i < adj[here].size(); i++) {
			int there = adj[here][i].first;
			int nextCost = adj[here][i].second + cost;

			if (dist[there] > nextCost) {
				dist[there] = nextCost;
				pq.push({ -nextCost, there });
			}
		}
	}

	return dist[arrive];
}

int main(void) {
	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int s, e, w;
		cin >> s >> e >> w;
		adj[s].push_back({ e, w });
	}

	int start, arrive;
	cin >> start >> arrive;

	cout << dijkstra(start, arrive) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 164 day