[Baekjoon] 1753번: 최단경로

🥅 문제

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

 

🔍 설계

adj_matrix를 사용하면, 20000*20000*4Byte로 메모리 초과가 발생한다. adj_list를 사용해야 한다.

 

우선순위 큐를 이용하여 어떤 점에서 갈 수 있는 점까지의 경로 중 작은 것부터 뽑는다. 이렇게 하면 뒤에 갱신하는 경로의 비용은 앞에 있는 경로의 길이보다 항상 크다. 따라서, 반복문의 최대 횟수는 간선의 개수인 300000이 된다.

 

👊 풀이

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int n, e, k, u, v, w, result = 0;
vector<vector<pair<int, int>>> adj_list(20001);
vector<int> dist(20001, 1e9 + 7);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

void Dijkstra() {
	dist[k] = 0;
	pq.push({ 0, k });
	while (!pq.empty()) {
		int cur_cost = pq.top().first;
		int cur_node = pq.top().second;
		pq.pop();
		for (int i = 0; i < adj_list[cur_node].size(); i++) {
			int next_node = adj_list[cur_node][i].second;
			int next_cost = cur_cost + adj_list[cur_node][i].first;
			if (dist[next_node] > next_cost) {
				dist[next_node] = next_cost;
				pq.push({ next_cost, next_node });
			}
		}
	}
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> e >> k;
	for (int i = 0; i < e; i++) {
		cin >> u >> v >> w;
		adj_list[u].push_back({ w, v });
	}

	Dijkstra();

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

	return 0;
}