[백준 BOJ1916] 최소비용 구하기 (C++)

1. 제목

- 백준 1916 최소비용 구하기

- BOJ 1916 최소비용 구하기

문제 링크 : 1916번: 최소비용 구하기 (acmicpc.net)

1916번: 최소비용 구하기

---

2. 풀이 과정

 

BOJ1753이랑 정말 똑같은 문제예요. 골드문제인데 다익스트라만 구현하면 그냥 바로 풀리는 문제예요. 풀이과정보다는 다익스트라 개념을 공부하는 게 이문제를 쉽게 푸는데 도움이 된다고 생각해요.

 

[알고리즘] 다익스트라 (C++) :: 별빛상자 (tistory.com)

[알고리즘] 다익스트라 (C++)

---

3. 코드

#define INF 1000000000

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

using namespace std;

int N, M;
int startIndex, endIndex;
vector <pair<int, int>> graph[1001];
int distances[1001];

void Dijkstra(int start)
{
	distances[start] = 0;
	priority_queue<pair<int, int>> pq;

	pq.push(make_pair(start, 0));
	while (!pq.empty())
	{
		int current = pq.top().first;
		int distance = -pq.top().second;
		pq.pop();
		
		//최단 거리가 아닌 경우 스킵
		if (distances[current] < distance) continue;
		for (int i = 0; i < graph[current].size(); i++)
		{
			// 선택된 노드의 인접 노드
			int next = graph[current][i].first;
			// 선택된 노드를 인접 노드로 거쳐서 가는 비용
			int nextDistance = distance + graph[current][i].second;
			// 기존의 최소 비용보다 더 저렴하다면 교체.
			if (nextDistance < distances[next])
			{
				distances[next] = nextDistance;
				pq.push(make_pair(next, -nextDistance));
			}
		}
	}
}

void Solution()
{
	for (int i = 1; i <= N; i++)
		distances[i] = INF;

	Dijkstra(startIndex);

	cout << distances[endIndex] << endl;	
}


void Input()
{
	cin >> N >> M;

	for (int i = 0; i < M; i++)
	{
		int from;
		int to;
		int distance;
		cin >> from >> to >> distance;
		graph[from].push_back(make_pair(to, distance));
	}
	cin >> startIndex >> endIndex;
}

int main()
{
	Input();
	Solution();

	return 0;
}