[알고리즘] c++ cpp 최소비용 구하기

포인트

1. 최단거리를 구하는 방법으로 다익스트라 알고리즘을 사용하였습니다. 
(모든 정점에서 최단거리를 구하는 것은 플로이드 와샬 알고리즘 - 다이나믹)

2. MST 하고 다른 것을 알면 좋다.

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> //min heap

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

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

using namespace std;

int n, m;
int s, e, c;
int start, arrive;
int dist[1001];
vector<pair<int, int>> map[1001];

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> s >> e >> c;
		map[s].push_back({c, e}); // 도시 간 연결 정보
	}
	cin >> start >> arrive;

	for (int i = 1; i <= n; i++) dist[i] = 987654321; // 초기값 설정은 불가능을 나타내는 이상치로 설정

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({0, start}); //시작점에 대한 설정
	dist[start] = 0;

	while (!pq.empty()) {
		int cost = pq.top().first; // 해당 도시까지의 최단거리값 저장해놓음
		int x = pq.top().second; // 이번에 검사할 도시와
		pq.pop();

		if (x == arrive) break; // 도착점 도달 시 그냥 종료

		for (int i = 0; i < map[x].size(); i++) {
			// 해당 도시에 연결된 다른 도시들 검사
			int ncost = map[x][i].first;
			int nx = map[x][i].second;
			if (dist[nx] > cost + ncost) {
				// 다른 도시들 중 최단거리 갱신할 수 있는 도시가 있다면
				dist[nx] = cost + ncost; // 업데이트 해주고
				pq.push({dist[nx], nx}); // 큐에 넣어줌 (거리에 - 를 붙여 최단거리 확인)
			}
		}
	}

	cout << dist[arrive] << endl;
}