1753번 최단경로

이 문제는 한 점에서 시작하여 다른 점들까지의 가장 짧은 경로를 탐색하는 것이 목적인 문제이다. 입력으로는 정점V의 개수와 간선의 개수E 그리고 시작이 될 정점 W가 주어진다.

이 문제에서는 다익스트라 라는 알고리즘을 이용하는데 각 점에서 다른점까지의 최소경로를 찾는데 이용하는 알고리즘이다.
다익스트라를 구현하는데는 2가지 방법이 있는데 2차원 배열을 이용하는 것과 최소힙을 이용하는 방법이다.
하지만 1753번은 2차원 배열 방법으로 문제를 풀려고 하면 메모리 초과가 난다. 정점이 최대 2만개 까지이기 때문인듯 하다.

그래서 최소힙을 사용하는 방법을 체택했다.
한점에서 다른점까지의 거리만 구하면 되므로 각 경로까지의 거리를 힙에 담아 거리를 갱신하는 것이다.

정답 코드

#include <iostream>
#include <queue>
#include <vector>
#include <utility>

#define INF 2000000

using namespace std;

vector<pair<int, int>>dots[20001];
int dist[20001];

void sol(int n, int m, int v) {
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
	pq.push(make_pair(0, v));
	dist[v] = 0;
	while (!pq.empty()) {
		int d = pq.top().first;
		int p = pq.top().second;
		pq.pop();
		for (auto i : dots[p]) {
			int linkd = d+i.first;
			int linkp = i.second;
			if (dist[linkp] > linkd) {
				dist[linkp] = linkd;
				pq.push(make_pair(linkd,linkp));
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n, m, v;
	cin >> n >> m >> v;
	for (int i = 1; i <= 20000; i++) dist[i] = INF;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		dots[a].push_back(make_pair(c, b));
	}
	sol(n,m,v);
	for (int i = 1; i <= n; i++) {
		if (dist[i] == INF) cout << "INF\n";
		else cout << dist[i] << '\n';
	}

	return 0;
}

이 문제를 풀면서 다익스트라 알고리즘에 대해 알게 되었고 우선순위큐가 구현이 돼어있다는 걸 깨닫게 됐다.