[BOJ-1916] 최소비용 구하기(C++)

백준 1916 최소비용

 

 

1916번: 최소비용 구하기

 

문제 설명

 

 - N개의 도시가 있다.

 

 - 한 도스에서 출발하여 다른 도시로 도착하는 M개의 버스가 있다.

 

 - A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려 한다.

 

 - A번째 도시에서 B번째 도시까지 가는 최소 비용을 출력하라.

 

 - 도시의 번호는 1번부터 N번까지이다.

---

 

입력 값

 

 - 첫째 줄에 도시의 개수 N( 1<= N <= 1,000 )이 주어진다.

 

 - 둘째 줄에는 버스의 개수 M( 1 <= M <= 100,000 )이 주어진다.

 

 - 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다.

   출발 도시의 번호 a, 도착 도시의 번호 b, 버스 비용 c( 0 <= c < 100,000 )

 

 - M+3째 줄에는 구하고자 하는 출발점의 도시번호와 도착점의 도시번호가 주어진다.

 

 - 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 출발 도시에서 도착 도시까지 가는데 최소 비용을 구해야 한다.

 

 - 모든 도시간 비용은 0이상이고, 도시 개수가 1000개 이하, 도시 간선이 10만개이기 때문에

   다익스트라 알고리즘을 사용하면 간단하게 구할 수 있다.

 

최단 경로 탐색 알고리즘 - 다익스트라(Dijkstra)

 

---

 

 

소스 코드

 

#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> boards[1001];

int visited[1001];

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

	int N, M, S, E;

	fill_n(visited, 1001, INT_MAX);

	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		boards[a].push_back({ b,c });
	}

	cin >> S >> E;

	priority_queue<pair<int, int>> pq;

	visited[S] = 0;
	pq.push({ 0,S });

	while (!pq.empty()){
		int nowIndex = pq.top().second;
		int nowCost = -pq.top().first;

		pq.pop();

		if (visited[nowIndex] < nowCost) {
			continue;
		}

		for (auto next : boards[nowIndex]) {
			int nextIndex = next.first;
			int nextCost = next.second;

			if (visited[nextIndex] > nowCost + nextCost) {
				visited[nextIndex] = nowCost + nextCost;
				pq.push({ -visited[nextIndex],nextIndex });
			}
		}

	}

	cout << visited[E] << endl;
    
	return 0;
}