백준 1753 최단경로 c++ // 다익스트라 알고리즘

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

1753번: 최단경로

1. 고찰

정석다익스트라 : O(V^2+E)

우선순위큐 다익스트라 : O(VElgE)

우선순위큐로 풀면된다.

 

2. 의사코드

1. q.push(0비용,시작정점)
2. 최소거리vertax 선택, 최단거리와다름->무쓸모->continue
3. v의 이웃에 대해, 이웃으로직진 > v로직진+이웃비용 -> 후자가 더짧음 -> d업뎃, q.push 
4.while(q.size()) 2~3반복

 

 

3. 전체코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int v, e,k;
vector<pair<int,int>> adj[20004];	//adj[1]:{2,3} 1->2로가는비용이 3임
int d[20004]; //시작~해당정점까지 최단거리
int INF = 987654321;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	fill(d, d + 20004, INF);
	cin >> v >> e >> k;
	while (e--) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({ w,v });
	}

	//{비용, 대상정점}
	priority_queue<pair<int, int>, 
					vector<pair<int, int>>,
					greater<pair<int, int>>> pq;
	d[k] = 0;
	pq.push({ d[k],k });
	while (pq.size()) {
		auto cur = pq.top(); pq.pop();
		//2. 해당 거리가 최단거리테이블값과 다르면
		//더짧은경로가 있음 -> 무쓸모 -> pass
		if (cur.first != d[cur.second]) continue;
		//3. 이웃한 정점들에대해 직진보다 현재정점을 거치는게 더 싸면 
		//d갱신, 큐에추가
		for (auto next : adj[cur.second]) {
			if (d[next.second] > d[cur.second]+next.first) {
				d[next.second] = d[cur.second] + next.first;
				pq.push({ d[next.second] ,next.second });
			}
		}
	}

	for (int i = 1; i <= v; ++i) {
		if (d[i] == INF) {
			cout << "INF\n";
			continue;
		}
		cout << d[i] << "\n";
	}
}