백준 1753번 : 최단경로

문제 링크 : www.acmicpc.net/problem/1753

내 풀이(2021.1.25.) : 다익스트라

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

#define MAX_V 20000 // 노드 개수의 최대값

int V, E, start_v; // V : 노드의 개수, E : 간선의 개수, start_v : 시작 노드
vector<pair<int, int>> VE_info[MAX_V + 1]; // V개의 노드들에 대한 <연결 노드, 간선 값> 쌍 (second = 특정 노드로부터 first번 노드까지의 간선값)
vector<int> shortest_distance(MAX_V + 1, INT_MAX); // 시작 노드로부터 V개의 도착 노드들까지의 최단 거리

void dijkstra(int start_v) { // 다익스트라
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
	// 최단 거리 비교를 위해 최소힙 사용 : <최단 거리, 노드 번호> 쌍 저장 및 정렬

	// 시작 노드의 최단 거리 확정
	shortest_distance[start_v] = 0; // 최단 거리 갱신
	heap.push(make_pair(0, start_v)); // 최단 거리 비교를 위해 <최단 거리, 노드 번호> 쌍을 힙에 삽입

	while (!heap.empty()) { // 모든 노드를 검사할 때까지
		pair<int, int> EV_info = heap.top(); heap.pop(); // 힙 내에서 최단 거리(first)가 가장 작은 <최단 거리, 노드 번호> 쌍
		int vertex = EV_info.second; // 도착 노드
		int distance = EV_info.first; // (현재로서의) 최단 거리
		if (distance > shortest_distance[vertex]) continue; // 이미 검사한 노드라면 무시
		
		// (continue문 아래 코드는 시작 노드를 제외한 나머지 V - 1개의 노드들에 대해 1번 수행)

		// vertex번 노드의 최단 거리 확정
		vector<pair<int, int>> info = VE_info[vertex]; // vertex번 노드에 대한 <연결 노드, 간선 값> 쌍
		for (int i = 0; i < info.size(); i++) {
			int v = info[i].first; // 연결 노드(v번 노드)
			int e = info[i].second; // 'vertex번 노드 -> v번 노드'의 간선값
			int new_dist = distance + e; // 최단 거리의 후보가 될 값
			if (new_dist < shortest_distance[v]) { // 최단 거리 갱신 여부 확인
				shortest_distance[v] = new_dist; // 최단 거리 갱신
				heap.push(make_pair(new_dist, v)); // 최단 거리 비교를 위해 <최단 거리, 노드 번호> 쌍을 힙에 삽입
			}
		}
	}
}

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

	cin >> V >> E >> start_v;
	// 노드/간선 정보 초기화
	for (int i = 0; i < E; i++) {
		int u, v, w; cin >> u >> v >> w;
		VE_info[u].push_back(make_pair(v, w));
	}

	// 최단 거리 초기화
	for (int i = 0; i < V; i++) {
		shortest_distance[i + 1] = INT_MAX;
	}

	// 다익스트라 알고리즘 수행
	dijkstra(start_v);

	// 최단 거리 출력
	for (int i = 0; i < V; i++) {
		if (shortest_distance[i + 1] == INT_MAX) cout << "INF" << "\n";
		else cout << shortest_distance[i + 1] << "\n";
	}

	return 0;
}

- 무향 그래프가 아닌 유향 그래프임을 기억할 것

- priority_queue의 default가 최대힙이므로, greater<pair<int, int>>를 이용해서 최소힙으로 바꿀 것

- VE_info[i]와 EV_info 둘다 pair<int, int> 타입이지만, 서로 전혀 다른 개념이므로 차이를 구분할 것

- '간선값'은 특정 노드와 특정 노드 사이에 있는 단 1개의 간선 가중치를 말하고, 최단 거리는 여러 간선값들의 합이므로, 이 둘의 개념의 차이를 명확하게 구분할 것