[c++/백준] 1753번: 최단경로

문제 링크

1753번: 최단경로

풀이

우선순위 큐를 이용한 다익스트라 문제
저번에 풀었던 최소 비용 구하기 문제랑 거의 같은 문제인데, 헷갈려서
우선순위 큐 마이너스 처리랑, 거리가 갱신 되지 않아도 우선순위 큐에 추가해서 메모리 초과났다.

1. dist의 초기값은 모두 무한대이고 시작 노드만 0으로 둔다.
2. 우선순위 큐 pq에 {0,k}값을 추가한다.
3. pq가 빌 때까지 반복하는데, d는 pq.top().first(현재 노드까지의 거리가 가장 작은 노드의 거리)에 마이너스 처리를 해주고(우선순위 큐는 내림차순인데 오름차순으로 구해야 해서), n은 pq.top().second(현재 노드까지의 거리가 가장 작은 노드)가 된다. 그리고 pq.pop()
   3-1. dist[n]보다 d가 크면 갱신할 필요가 없기 때문에 continue
   3-2. 현재 노드 n과 연결된 노드들을 확인하면서 거리가 작은 값으로 갱신 되는 것들만 dist[next]값을 갱신시키고 pq에 넣어준다.
4. dist를 출력하면 끝.

코드

#include <iostream>
#include <queue>
#include <vector>
#define MAX 3000000

using namespace std;

vector<vector<pair<int,int>>> arr;
priority_queue<pair<int, int>> pq;
vector<int> dist;

void dijkstra(int k)
{
	dist[k] = 0;
	pq.push({ 0,k });
	while (!pq.empty()) {
		int d = -pq.top().first;
		int n = pq.top().second;
		pq.pop();
		
		if (dist[n] < d) continue;
		for (int i = 0;i < arr[n].size();i++) {
			int next = arr[n][i].first;
			int next_dist = arr[n][i].second;
			if (dist[next] > dist[n] + next_dist) {
				dist[next] = dist[n] + next_dist;
				pq.push({ -dist[next], next });
			}
		}
	}
}

int main()
{
	int V, E, K;
	cin >> V >> E >> K;

	arr.resize(V+1);
	dist.resize(V + 1,MAX);

	for (int i = 0;i < E;i++) {
		int u, v, w;
		cin >> u >> v >> w;
		arr[u].push_back({ v,w });
	}
	dijkstra(K);

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

	return 0;
}