[BOJ/C++] 1916 최소비용 구하기

문제

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

풀이

💡다익스트라

• 최소 비용 구하는 문제
• weighted graph

1. dist 배열을 선언해서 최댓값으로 초기화해주기
2. 우선순위큐를 선언에서 탐색 진행
   • 우선순위큐는 (cost, node) 형태로 넣기
   • 최소힙을 구현하기 위해 cost에 minus 붙여서 변수값 선언

⚠️ 시간복잡도를 줄이기 이위해 visited 배열 선언해서 이미 탐색한 부분은 skip 해줘야함

dist 배열 및 우선순위큐 동작 방식

dist = MAX, MAX, MAX, MAX, MAX

dist(1);
dist = 0, MAX, MAX, MAX, MAX
큐 : (0, 1)
(0, 1) pop

dist = 0, 2, 3, 1, 10
큐 : (2, 2), (3, 3), (1, 4), (10, 5)

최소값인 (1, 4) pop
4와 연결된 5 확인 : 기존값 vs dist[4] + 4->5
최소값 갱신하면 큐에 push 해주고, 계속 탐색 진행

최소 비용 경로 출력

코드

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

using namespace std;

vector<pair<int, int>> v[1001];
int dist[1001];
bool visited[1001];

void dijkstra(int node) {
	priority_queue<pair<int, int>> pq;
	pq.push({ 0, node });
	dist[node] = 0;

	while (!pq.empty()) {
		int cost = -pq.top().first;
		int cur = pq.top().second;

		pq.pop();
		
		if (visited[cur])	continue;
		visited[cur] = true;

		for (int i = 0; i < v[cur].size(); i++) {
			int next = v[cur][i].first;
			int new_cost = v[cur][i].second + cost;
			if (dist[next] > new_cost) {
				dist[next] = new_cost;
				pq.push({ -dist[next], next });
			}
		}
	}
}

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

	int N, M;
	cin >> N >> M;

	for (int i = 0; i <= N; i++) {
		dist[i] = INT_MAX;
	}

	for (int i = 0; i < M; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;
		v[from].push_back({to, cost});
	}

	int start, destination;
	cin >> start >> destination;

	dijkstra(start);
	cout << dist[destination];

	return 0;
}