[백준 1753] 최단경로

https://acmicpc.net/problem/1753

 

---

해설

이번 문제는 한 정점에서의 다른 정점들의 최단 거리를 구하는 다익스트라 알고리즘을 적용하는 문제이다.

다익스트라 알고리즘을 구현할 수있다면 바로 풀리는 문제이니 참고바란다.

다익스트라를 모른다면, 풀기 힘들 수도 있으니 구글링으로 다익스트라의 구현법을 어느정도 알고 오는 것을 추천한다.

 

 

˙˙˙

 

소스코드

 

#include <iostream>
#include <queue>
using namespace std;
const int mn = 2e4;
const int INF = 1e9;
vector<pair<int, int> > g[mn];
int dist[mn];
int main(){
	int n, m; cin >> n >> m;
	int k; 
    cin >> k;
	k--;
	for(int i=0; i<m; i++){
		int u,v,w; 
        cin >> u >> v >> w;
		u--, v--;
		g[u].push_back({v,w});
	}
	for(int i=0; i<n; i++)
		dist[i] = INF;
	using p = pair<int, int>;
	priority_queue<p, vector<p>, greater<p> >pq;
	pq.push({0,k});
	dist[k] = 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(pair<int, int> 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});
			}
		}
	} 
    
	for(int i=0; i<n; i++){
		if(dist[i] == INF) 
        	cout << "INF" << '\n';
		else cout << dist[i] << '\n';
	}
}

 

유사 문제 : 백준 1916 최소비용 구하기 ( https://www.acmicpc.net/problem/1916 )