[백준/BOJ] 백준 1916번 : 최소비용 구하기

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

1916번: 최소비용 구하기

도시들을 정점, 버스들을 간선, 버스 비용을 간선의 가중치로 생각하여 다익스트라 알고리즘을 통해 출발 도시에서 각 도시로 가는 최소 비용을 구하고 그중 도착 도시로 가는 최소비용을 구하였다.

 

코드

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

int n, m;

vector<pair<int, int>> adj[1000]; //pair:비용, 도착지 순서로 저장

// start도시부터 stop도시까지 가는 최소 비용을 구한다
int Solve(int start, int stop)
{
	//start도시부터 각각 도시로가는 최소비용을 저장
	//매우 큰 수 987654321로 초기화
	vector<int> result(n,987654321);

	//pair:-(지금까지 구한 최소비용),도착지 순서로 저장
	//-(지금까지 구한 최소비용) 저장하는 이유는 지금까지 구한 최소비용이 작은것 부터 뽑기 위해서
	priority_queue<pair<int, int>> pq;

	//자신의 위치까지 가는 최소비용은 0
	result[start] = 0;
	pq.push(make_pair(-0, start));

	while (!pq.empty())
	{
		int here = pq.top().second;
		int here_cost = -pq.top().first;
		pq.pop();

		//here도시에 더 작은 최소비용으로 이미 갱신되었을때
		if (result[here] < here_cost)
			continue;

		//here에서 갈수 있는 도시들을 확인한다
		for (int i = 0; i < adj[here].size(); i++)
		{
			int there = adj[here][i].second;
			int there_cost = adj[here][i].first + here_cost;

			//there도시까지 가는 더 작은 최소비용을 발견 했을때
			if (result[there] > there_cost)
			{
				//최소비용 업데이트
				result[there] = there_cost;

				//우선순위 큐에 저장
				pq.push(make_pair(-there_cost, there));
			}
		}

	}

	//stop도시까지 가는 최소 비용을 반환한다
	return result[stop];

}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int bus_start, bus_stop, cost;
	int start, stop;

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		cin >> bus_start >> bus_stop >> cost;

		//도시의 번호를 0부터 매기기 위해 bus_start와 bus_stop에 -1을 하였다
		adj[bus_start -1].push_back(make_pair(cost, bus_stop -1));
	}
	
	cin >> start >> stop;

	//도시의 번호를 0부터 매기므로 start와 stop에 -1을 하였다
	cout << Solve(start - 1, stop - 1);

	return 0;
}