[백준] 최단경로 (1753번)

ㅁㄴㅇㅁㄴㅇ

---

 

다익스트라의 기본 격인 문제이다.

시작점이 주어지므로 해당하는 시작점부터 다른 노드들까지의 최단 경로를 구하자.

우선 거리를 저장할 dist 배열을 INF로 초기화한다. 그 후 다익스트라를 실행하자.

start의 거리를 0으로 설정한 후 최소힙을 선언한다.

큐는 현재까지의 거리와 현재 위치를 pair로 저장한다. 최소힙으로 선언했기 때문에 거리가 짧은 곳부터 읽게된다.

 

큐에서 top에 있는 값을 꺼낸 후 해당 위치와 연결된 다른 노드들을 모두 검사하면서 현재까지 거리와 해당하는 곳 까지의 거리를 합한 게 더 작다면 최신화해주고 해당 노드를 방문한다.

이렇게 모든 노드를 방문하면 모든 지점까지의 최단 거리를 알 수 있다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C%20(1753%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int V, E;
int start;
vector<pair<int, int>> v[20001]; //v[a] = (b,c) : a부터 b까지 c의 거리
int dist[20001];

void dijk() {
	dist[start] = 0;
	priority_queue<pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> q; //거리, 시작점, 최소힙으로 선언
	q.push({ 0, start });
	while (!q.empty()) {
		int x = q.top().second;
		int d = q.top().first;
		q.pop();
		
		for (int i = 0; i < v[x].size(); i++) {
			int nx = v[x][i].first;
			int nd = v[x][i].second;
			if (dist[nx] > dist[x] + nd) {
				dist[nx] = dist[x] + nd;
				q.push({ dist[nx], nx });
			}
		}
	}
}

int main()
{
	cin >> V >> E >> start;
	for (int a,b,c,i = 0; i < E; i++) {
		cin >> a >> b >> c;
		v[a].push_back({ b,c });
	}

	for (int i = 1; i <= V; i++)
		dist[i] = 987654321;
	dijk();

	for (int i = 1; i <= V; i++)
		if (dist[i] == 987654321)
			cout << "INF\n";
		else
			cout << dist[i] << "\n";
	
}