[백준] 1753번: 최단 경로

📌 문제

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

📌 설명

가장 대표적인 다익스트라 문제이다. 우선순위 큐를 통해 구현하였다.

📌 코드

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

#define INF 300001

using namespace std;

int main() {
	int v, e, k;
	cin >> v >> e >> k;

	vector<pair<int, int>> nodes[20001]; // {도착 노드, 가중치}
	for (int i = 0;i < e;i++) {
		int x, y, w;
		cin >> x >> y >> w;
		nodes[x].push_back({ y,w });
	}

	vector<int> cost(v + 1);
	for (int i = 1;i <= v;i++) {
		if (i == k)
			cost[i] = 0;
		else
			cost[i] = INF;
	}

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ 0, k });
	while (!pq.empty()) {
		int weight = pq.top().first;
		int cur = pq.top().second;
		pq.pop();

		// 이미 최단거리가 존재하는 경우
		if (cost[cur] < weight)
			continue;

		for (int i = 0;i < nodes[cur].size();i++) {
			if (weight + nodes[cur][i].second < cost[nodes[cur][i].first]) {
				cost[nodes[cur][i].first] = weight + nodes[cur][i].second;
				pq.push({ weight + nodes[cur][i].second ,nodes[cur][i].first });
			}
		}
	}

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

import sys
import heapq
input=sys.stdin.readline

n,m=map(int,input().split())
start=int(input())

graph=[[] for _ in range(n+1)]

inf=300001
dist=[inf]*(n+1)
dist[start]=0

for _ in range(m):
    u,v,w=map(int,input().split())
    graph[u].append((v,w))

q=[]
heapq.heappush(q,(0,start))
while(q):
    w,cur=heapq.heappop(q)

    if dist[cur]<w:
        continue

    for nxt,nw in graph[cur]:
        if w+nw<dist[nxt]:
            dist[nxt]=w+nw
            heapq.heappush(q,(dist[nxt],nxt))

for d in dist[1:]:
    if d==inf:
        print("INF")
    else:
        print(d)

---

#define INF 300001

적당히 큰 수로 INF를 정의한다.

	vector<pair<int, int>> nodes[20001]; // {도착 노드, 가중치}
	for (int i = 0;i < e;i++) {
		int x, y, w;
		cin >> x >> y >> w;
		nodes[x].push_back({ y,w });
	}

인접 리스트로 노드들의 정보를 관리한다.

	vector<int> cost(v + 1);
	for (int i = 1;i <= v;i++) {
		if (i == k)
			cost[i] = 0;
		else
			cost[i] = INF;
	}

cost는 시작 노드에서 특정 노드 간 최단 거리를 저장한다. 시작 노드는 0으로 설정하고 나머지 노드는 INF로 초기화한다.

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ 0, k });

우선순위 큐를 선언하고 시작 노드와 가중치를 넣는다. 우선순위 큐 요소의 첫 번째는 가중치가 위치해야 한다. 가중치를 기준으로 정렬되어야 하기 때문이다.

		// 이미 최단거리가 존재하는 경우
		if (cost[cur] < weight)
			continue;

cur은 현재 노드, weight는 현재 노드까지 최소 거리이다. cost[cur] < weight는 이미 cur에 대한 최단 거리가 정의되었다는 것이다. 우선순위 큐 특성 상 최소 가중치를 가진 노드부터 먼저 처리한다. 따라서 이후 과정을 진행하지 않는다.

		for (int i = 0;i < nodes[cur].size();i++) {
			if (weight + nodes[cur][i].second < cost[nodes[cur][i].first]) {
				cost[nodes[cur][i].first] = weight + nodes[cur][i].second;
				pq.push({ weight + nodes[cur][i].second ,nodes[cur][i].first });
			}
		}

nodes[cur][i].first는 다음 노드(cur과 인접한 노드), nodes[cur][i].second는 cur에서 다음 노드까지의 가중치이다. if문의 조건은 시작 노드에서 nodes[cur][i].first로 갈 때 cur을 경유하는 것이 그렇지 않은 경우보다 최단 거리인지 확인한다. 만약 그렇다면 nodes[cur][i].first의 cost 배열을 최단 거리로 초기화하고 pq에 삽입한다.