백준 1753번 최단경로

< 백준 1753번 최단경로 - 마포 코딩박 >

사용한 알고리즘: 다익스트라


 시작 정점 K에서 각 정점까지의 최단 경로의 경로값을 출력하는 문제였습니다. 저는 다익스트라를 이용해 해결하였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 13~19)
 시작정점 K에서 < i번 정점까지, w의 경로값만큼 걸린다 > 를 저장할 pq를 만듭니다.
 경로값이 작은게 위로 오게 만듭니다.

(2) (코드 30~50)
 시작정점 K를 제외한 나머지 정점까지의 경로값을 모두 Infimum으로 바꾸고 시작합니다.
 pq에는 초기에 < K(자기자신), 0(경로값=0) > 을 넣고 시작합니다.
 pq에서 하나씩 빼보며, 해당 정점과 연결된 정점들의 경로값들을 최신화해줍니다.

	#include <iostream>
	#include <vector>
	#include <utility>
	#include <queue>
	using namespace std;
	// 다익스트라
	#define pii pair<int, int>
	const int INF = 1000000000;
	int V, E, K;
	// num[a] : < a->b번 정점 연결 , w 경로값 > 으로 저장
	vector<pii> num[20003];
	int ans[20003];
	// 작은 값 먼저
	struct cmp{
	bool operator()(pii t, pii u){
	return t.second > u.second;
	}
	};
	// < i번 노드까지, W 만큼 경로값 >
	priority_queue<pii, vector<pii>, cmp> QQ;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> V >> E >> K;
	for (int i = 0; i < E; ++i){
	int a, b, w;
	cin >> a >> b >> w;
	num[a].push_back(pii(b,w));
	}
	for (int i = 1; i <= V; ++i) ans[i] = INF;
	// 시작점 에서 시작점 까지는 경로값이 0
	ans[K] = 0;
	QQ.push(pii(K,0));
	while(!QQ.empty()){
	int now = QQ.top().first;
	int ww = QQ.top().second;
	QQ.pop();
	// 중복 방지 역할
	if(ww>ans[now])
	continue;
	for (int i = 0; i < num[now].size(); ++i){
	int ch = num[now][i].first;
	int chww = num[now][i].second;
	if(ww+chww < ans[ch]){
	ans[ch] = ww+chww;
	QQ.push(pii(ch,ww+chww));
	}
	}
	}
	for (int i = 1; i <= V; ++i){
	if(ans[i]==INF)
	cout << "INF" << '\n';
	else
	cout << ans[i] << '\n';
	}
	return 0;
	}

view raw BOJ 1753.cpp hosted with ❤ by GitHub