[BOJ] 백준 1753 - 최단경로

문제 링크 

1753번: 최단경로

방향 그래프의 한 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 문제이다.

 

해당 문제는 Dijkstra 알고리즘을 사용하여 풀이했다.

 

Dijkstra 알고리즘에 대한 설명은 아래 링크에서 확인할 수 있다.

2021.04.06 - [Algorithm/Theory] - [Algorithm] Dijkstra Algorithm (다익스트라 알고리즘)

[Algorithm] Dijkstra Algorithm (다익스트라 알고리즘)

풀이는 다음과 같다.

풀이에서는 메모리 제약상 인접 행렬(Adjacency Matrix)이 아닌 인접 리스트(Adjacency List)로 구현했다.

또한, Min Heap 대신 dist 값에 음을 취해 구현하였다.

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

#define INF 2100000000

using namespace std;

int min(int a, int b) {
	return a < b ? a : b;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int v, e, start;
	priority_queue<pair<int,int>> pq;
	// first: destination, second: weight
	vector<vector<pair<int,int>>> edge;
	vector<int> dist;

	cin >> v >> e;

	edge.resize(v + 1);
	dist.resize(v + 1, INF);

	cin >> start;
	for (int i = 0; i < e; i++) {
		int a, b, d;
		cin >> a >> b >> d;
		edge[a].push_back(make_pair(b, d));
	}
	dist[start] = 0;
	pq.push(make_pair(0, start));
	while (!pq.empty()) {
		int node = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();
		int size = edge[node].size();
		for (int i = 0; i < size; i++) {
			int dest = edge[node][i].first;
			int weight = edge[node][i].second;
			if (dist[dest] > dist[node] + weight) {
				dist[dest] = dist[node] + weight;
				pq.push(make_pair(-dist[dest], dest));
			}
		}
	}
	for (int i = 1; i <= v; i++) {
		if (dist[i] == INF) {
			cout << "INF\n";
		}
		else {
			cout << dist[i] << "\n";
		}
	}
}