[백준] 골5 - 최소비용 구하기

1916번: 최소비용 구하기

문제 설명

풀이

단일 시작점 최단경로이므로 다익스트라 알고리즘을 사용할 수 있다. 다익스트라 알고리즘의 시간 복잡도는

O((V+E)log V) 이므로 시간 제한 문제도 해결된다.

시작점에서 모든 정점의 최단거리를 담는 배열이 필요하다.(dist)

초기값은 infinity로 설정하여 매번 갱신할 수 있게 한다.

코드

#include <bits/stdc++.h>
using namespace std;

int n;
int m;
int s, e, w;
int answer_s, answer_e;
int dist[1001];

typedef pair<int, int> pii;
vector<pair<int, int>> v[1001]; // index: start // first: end // second: weight

void Dijkstra(int start)
{
	dist[start] = 0;

	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({ dist[start], start });

	while (!pq.empty())
	{
		int c = pq.top().second;
		int w = pq.top().first;
		pq.pop();

		if (w > dist[c])
			continue;
		
		for (auto e : v[c])
		{
			int next_c = e.first;
			int next_w = w + e.second;

			if (next_w < dist[next_c])
			{
				dist[next_c] = next_w;
				pq.push({ next_w, next_c });
			}
		}
	}
}

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

	for (int i = 1; i <= 1000; i++)
		dist[i] = INT_MAX;

	cin >> n;
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> s >> e >> w;
		v[s].push_back({ e, w });
	}
	cin >> answer_s >> answer_e;

	Dijkstra(answer_s);

	cout << dist[answer_e];
	return 0;
}

소감

다익스트라 알고리즘을 조금씩 풀어봐야겠다. 가장 기본적인 문제인데 reference를 참조했다. 어느정도 문제를 푼 뒤 다익스트라 알고리즘을 집중적으로 풀어봐야겠다.

참조

[백준] 1916번 - 최소비용 구하기

[백준] 골4 - 특정한 최단 경로

1504번: 특정한 최단 경로

문제 설명