[백준] 1753번 - 최단경로

백준 1753번 최단경로

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

---

코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define mx 20001
#define INF 987654321
using namespace std;

int V,E,K;
vector<pair<int,int>> v[mx];
priority_queue<pair<int,int>> pq; 
int dp[mx];

int main(){ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin >> V >> E >> K;
	fill(dp+1,dp+1+V,INF);
	for(int i=0;i<E;i++){
		int a,b,c;
		cin >> a >> b >> c;
		v[a].push_back({b,c});
	}
	dp[K]=0;
	pq.push({0,K});
	while(!pq.empty()){
		int cur = pq.top().second;
		pq.pop();
		for(int i=0;i<v[cur].size();i++){
			int cost = v[cur][i].second;
			int next = v[cur][i].first;
			if(dp[next] > dp[cur]+cost){
				dp[next] = dp[cur]+cost;
				pq.push({-dp[next],next});
			}
		}
	}
	for(int i=1;i<=V;i++){
		if(dp[i]==INF)
			cout << "INF\n";
		else
			cout << dp[i] << "\n";
	}
}

---

풀이

다익스트라를 이용한 기본 문제