백준 1916 c++

오랜만에 풀어본 다익스트라 문제이다. 가중치가 포함된 최단거리, 최소비용 문제는 다익스트라로 풀 수 있다.
다익스트라, 위상정렬을 계속 진행하겠다.

참고
https://www.youtube.com/watch?v=611B-9zk2o4&t
https://blog.naver.com/ndb796/221234424646

#include <iostream>
#include <vector>
#include <queue>//우선순위 큐 사용

using namespace std;

void input_data(vector<vector<pair<int, int>>> &bus_fare, int *start, int *destination)
{
	//cout << "input_data()\n";
	int N, M;
	int A, B, cost;
	int i;

	cin >> N >> M;
	bus_fare.resize(N + 1);
	for (i = 0; i < M; i++)
	{
		cin >> A >> B >> cost;
		bus_fare[A].push_back({B, cost});
	}
	cin >> *start >> *destination;

	//cout << "\n입력 결과\n";
	//for (i = 1; i < bus_fare.size(); i++)
	//{
	//	cout << "출발 : " << i << "\t";
	//	for (int j = 0; j < bus_fare[i].size(); j++)
	//	{
	//		cout << "[도착 : " << bus_fare[i][j].first << " 요금 : " << bus_fare[i][j].second << "]\t";
	//	}
	//	cout << "\n";
	//}
	//cout << "\n";

	return;
}

void dijkstra(vector<vector<pair<int, int>>>& bus_fare, int start, vector<int>& answer)
{
	//cout << "dijkstra()\n";
	int i;
	priority_queue<pair<int, int>> q;
	int current, next;
	int cost, next_cost;
	
	answer[start] = 0;
	q.push({ start, 0 });
	while (!q.empty())
	{
		current = q.top().first;
		cost = q.top().second;
		q.pop();
		if (answer[current] < cost)//현재 요금액이 기존 요금액보다 비싸면?
		{
			continue;//통과
		}
		else
		{
			for (i = 0; i < bus_fare[current].size(); i++)
			{
				next = bus_fare[current][i].first;
				next_cost = cost + bus_fare[current][i].second;
				if (next_cost < answer[next])//다음 가격이 기존의 다음 가격보다 저렴하면 교체
				{
					answer[next] = next_cost;
					q.push({next, next_cost});
				}
			}
		}
		//cout << "현 위치 : " << current << "\t";
		//for (int temp : answer)
		//{
		//	cout << temp << " ";
		//}
		//cout << "\n";
	}
	//cout << "다익스트라 결과\n";
	//for (int temp : answer)
	//{
	//	cout << temp << " ";
	//}
	//cout << "\n";

	return;
}

void find_answer(vector<vector<pair<int, int>>>& bus_fare, int start, int destination)
{
	//cout << "find_answer()\n";
	int N = bus_fare.size();
	vector<int> answer(N, 1000000001);

	dijkstra(bus_fare, start, answer);
	cout << answer[destination] << "\n";

	return;
}

//다익스트라 알고리즘!!!
int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int start, destination;
	vector<vector<pair<int, int>>> bus_fare;

	input_data(bus_fare, &start, &destination);
	find_answer(bus_fare, start, destination);

	return 0;
}