[G5] 백준 5972번 택배 배송 C++ 최단 경로, 다익스트라

리뷰

 

간단한 다익스트라를 통한 시작점 > 도착점으로 가는 최단 경로를 구하는 문제

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

 

전역 변수

• n, m : 노드의 개수를 저장할 정수형 변수 n, 간선 개수를 저장할 정수형 변수 m
• Pos : 간선 정보를 저장할 구조체, 다음 노드와 가중치가 저장되며, 우선순위 큐의 compare 함수를 정의했다.
• path : 각 노드의 인접리스트를 저장할 Pos타입 2차원 벡터

 

함수

1. dijkstra

int dijkstra(int start, int end)

 

1. start에서 end까지의 최단 경로를 구하는 함수
2. Pos타입 우선순위 큐 pq에 start를 삽입하고 end까지 가는길의 최단경로를 dist벡터에 최신화 해준다.
3. pq가 빌때까지 while루프를 통해 위 작업을 반복하고 최종적으로 dist에 저장된 end노드의 거리를 리턴한다.

 

문제풀이

1. n, m값을 입력 받고 path의 사이즈를 n + 1로 초기화 해준다.
2. m번의 반복문을 걸쳐 path 벡터에 양방향 간선을 추가해 준다.
3. 다익스트라에 매개변수를 1과 n을 넣어준 후 리턴값을 출력해 준다.

 

참고 사항

1-based-indexing이 적용된다. 노드를 초기화 할때 참고

 

정답 코드

#include<iostream>
#include<queue>

using namespace std;
int n, m;

struct Pos {
	int node, yeomul;
	bool operator<(const Pos& other) const {
		return yeomul > other.yeomul;
	}
};
vector<vector<Pos>> path;

int dijkstra(int start, int end) {
	priority_queue<Pos> pq;
	pq.push({ start, 0 });
	vector<int> dist(n + 1, 2e9);
	dist[start] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cn = pos.node, cd = pos.yeomul;
		if (dist[cn] != cd) continue;
		for (Pos next : path[cn]) {
			int nn = next.node, nd = next.yeomul;
			if (dist[nn] > cd + nd) {
				dist[nn] = cd + nd;
				pq.push({ nn, dist[nn] });
			}
		}
	}
	return dist[end];
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	path.resize(n + 1);
	while (m--) {
		int a, b, c; cin >> a >> b >> c;
		path[a].push_back({ b, c });
		path[b].push_back({ a, c });
	}
	cout << dijkstra(1, n);
}