백준 1916 - 최소비용 구하기(C++)

문제

정점 N개와 M개의 간선이 주어진다. A번째 정점에서 B번째 정점까지 도달하는 데 드는 최소 비용을 출력하라.

입력

첫째 줄에 N(1 <= N <= 1,000), 둘째 줄에 M(1 <= M <= 100,000)이 주어진다.

 

셋째 줄부터 M개의 줄에 간선과 가중치에 대한 정보가 주어지고 이때 가중치의 크기는 0 <= C <= 100,000이다.

 

마지막 줄에 출발점 A와 도착점 B가 주어진다.

 

예제 입력

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

예제 출력

4

문제 해결

어디서 힌트를 얻을 수 있을까?

 

문제에서 정점, 간선, 가중치, 그리고 최소 비용이라는 단어를 통해 이 문제는 다익스트라 알고리즘을 이용하여 문제를 풀 수 있다는 것을 알 수 있다. 이때 가중치의 비용은 자연수이므로 다익스트라의 음수를 포함하지 못한다는 문제점을 고려할 필요가 없었다.

 

단순히 다익스트라를 구현할 수 있냐 없냐의 문제이기 때문에 코드는 다음과 같다.

코드

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

typedef std::pair<int, int> P;
std::vector<P> varr[1001];
long long dist[1001];
long long INF = 999987654321;

void Dijkstra(int S)
{
	std::priority_queue<P > pq;
	pq.push(P(0, S));
	dist[S] = 0;
	while (!pq.empty())
	{
		int here = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();
		if (cost > dist[here])
			continue;
		for (int i = 0; i < varr[here].size(); i++)
		{
			int there = varr[here][i].first;
			int nCost = cost + varr[here][i].second;
			if (dist[there] > nCost)
			{
				dist[there] = nCost;
				pq.push(P(-nCost, there));
			}
		}
	}

}

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int N, M;
	std::cin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		int X, Y, C;
		std::cin >> X >> Y >> C;
		varr[X].push_back(P(Y, C));
	}
	for (int i = 0; i < N + 1; i++)
		dist[i] = INF;
	int S, D;
	std::cin >> S >> D;
	Dijkstra(S);
	std::cout << dist[D] << std::endl;
	return 0;
}

문제 출처

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

1916번: 최소비용 구하기

이론

https://deulee.tistory.com/10

다익스트라(Dijkstra) 알고리즘