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

구현 방식

• 다익스트라로 푼다.
• dist를 초기화할 때 fill(&dist[0], &dist[MAXSIZE-1], INT_MAX); 로 해버려서 마지막게 0으로 초기화되어서 헤맸었다.
• 다음에는 실수하지말자..

코드

• 최종 코드는 아래와 같다.

#include <bits/stdc++.h>

using namespace std;


void solution(int N, int start, int end, vector<vector<pair<int, int>>>& graph);
void dijkstra(int start, vector<vector<pair<int, int>>>& graph);

const int MAXSIZE = 1001;
int dist[MAXSIZE] = {};

int main() {
	int N, M;
	int start, end;
	cin >> N >> M;
	vector<vector<pair<int,int>>> graph(N+1);

	for (int i = 0; i < M; i++)
	{
		int sbus, ebus, w;
		cin >> sbus >> ebus >> w;
		graph[sbus].push_back({ebus, w});
	}

	cin >> start >> end;
	solution(N, start, end, graph);

}


void solution(int N, int start, int end, vector<vector<pair<int, int>>>& graph)
{
	fill(&dist[0], &dist[MAXSIZE], INT_MAX);
	dijkstra(start, graph);
	cout << dist[end];

}

void dijkstra(int start, vector<vector<pair<int, int>>>& graph)
{
	// w , idx
	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 currWeight = pq.top().first;
		int currCity = pq.top().second;
		pq.pop();

		if (dist[currCity] < currWeight) continue;

		for (auto& next : graph[currCity])
		{
			int nextCity = next.first;
			int nextWeight = next.second;
			if (currWeight + nextWeight < dist[nextCity])
			{
				dist[nextCity] = currWeight + nextWeight;
				pq.push({ dist[nextCity] , nextCity });
			}
		}
	}
}