[C++][백준] 최소비용 구하기(1916) - 기본 다익스트라

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.

 

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

 

풀이

다익스트라 기본 문제입니다.

 

전체 코드는 아래와 같습니다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAX = 1010;
int N, M; // 도시, 버스
vector<int> myGraph[MAX];
vector<int> myCost[MAX];

int cost[MAX];
int start_node, end_node;

struct myData {
	int node;
	int cost;
};

struct comp {
	bool operator()(myData a, myData b) {
		if (a.cost == b.cost) {
			return a.node > b.node;
		}
		else {
			return a.cost > b.cost;
		}
	}
};

void init() {
	// 기본적으로 연결되지 않은 경우 비용은 무한이다.
	for (int i = 0; i < MAX; i++) {
		cost[i] = 987654321;
	}
}

void dijkstra() {
	cost[start_node] = 0;
	priority_queue<myData, vector<myData>, comp> myPQ;
	myPQ.push({ start_node, 0 });

	while (!myPQ.empty()) {
		int cur_node = myPQ.top().node;
		int cur_cost = myPQ.top().cost;
		myPQ.pop();

		// 최단 거리가 아니라면 스킵합니다.(이미 갱신된 경우)
		if (cost[cur_node] < cur_cost) continue;

		for (int i = 0; i < myGraph[cur_node].size(); i++) {
			int next_node = myGraph[cur_node][i];
			int next_cost = myCost[cur_node][i]; // 현재 노드를 거쳐서 다음 노드로 가는 비용

			// 기존의 최소 비용보다 더 저렴하다면 교체합니다.
			if (cost[next_node] > cur_cost + next_cost) {
				cost[next_node] = cur_cost + next_cost;
				myPQ.push({ next_node, cur_cost + next_cost });
			}
		}
	}

}

int main() {
	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int start, end, cost;
		cin >> start >> end >> cost;
		myGraph[start].push_back(end);
		myCost[start].push_back(cost);
	}
	cin >> start_node >> end_node;

	init();
	dijkstra();

	cout << cost[end_node];

	return 0;
}