[백준 1916] 최소비용 구하기

https://acmicpc.net/problem/1916

---

해설

이 문제는 전에 풀었던 백준 1753 최단경로 문제와 동일하게 다익스트라 알고리즘을 사용해서 푸는 문제이다.

다익스트라의 개념을 모르면 풀기 힘들수도 있으니 다익스트라에 대해 구글링해서 구현법을 꼭 익히고 오길 바란다.

 

처음 지점으로 다익스트라를 돌리고 마지막에 처음지점과 도착 지점의 거리만 출력해주면 끝이다.

 

˙˙˙

 

소스코드

 

#include <iostream>
#include <vector>
#include <queue>
const int mn = 1e3;
const int INF = 1e9;
using namespace std;
using p = pair<int, int>;
vector<p> g[mn];
int dist[mn];
void init(int n) {
	for (int i = 0; i < n; i++)
		dist[i] = INF; 
}
int main() {
	int n, m; cin >> n >> m;
	init(n);
	for (int i = 0; i < m; i++) {
		int u, v, w;
        cin >> u >> v >> w;
		u--;
        v--;
		g[u].push_back({v, w});
	}
	int ks, kf; cin >> ks >> kf;
	ks--;
	priority_queue<p, vector<p>, greater<p> > pq;
	pq.push({ 0, ks });
	dist[ks] = 0;
	while (!pq.empty()) {
		p top = pq.top();
        pq.pop();
		int cur_dist = top.first;
		int cur = top.second;
		if (dist[cur] < cur_dist) 
        continue;
		for (p nxt_edge : g[cur]) {
			int nxt = nxt_edge.first;
			if (dist[nxt] > dist[cur] + nxt_edge.second) {
				dist[nxt] = dist[cur] + nxt_edge.second;
				pq.push({ dist[nxt], nxt });
			}
		}
	}
	cout << dist[kf-1] << '\n';
}

 

유사 문제 : 백준 1753 최단경로 ( https://acmicpc.net/problem/1753 )