[백준/C++] 1916. 최소비용 구하기

문제 

www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

풀이

다익스트라 알고리즘을 이용해서 풀었다. 

시간 복잡도를 낮추기 위해 힙을 이용해 구현했다. 

시간복잡도 : 노드가 V,간선이 E개 일 때, O(E*logV)

 

백지 상태에서 구현하려니 생각이 나지 않아서, 저번에 구현해뒀던 코드를 충분히 숙지한 후에 구현해보았다.

코드

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

using namespace std;

#define INF 987654321

vector<pair<int, int>> adjs[1001];
int min_dist[1001];

void Dijkstra(int start) {
	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, start));
	min_dist[start] = 0; //////

	while (!pq.empty()) {
		int cost = -pq.top().first;
		int cur = pq.top().second;
		pq.pop();/////
		if (min_dist[cur] < cost) continue;

		for (int i = 0;i < adjs[cur].size();i++) {
			int there = adjs[cur][i].first;
			int new_cost = cost + adjs[cur][i].second;
			if (min_dist[there] > new_cost) {
				min_dist[there] = new_cost;
				pq.push(make_pair(-new_cost, there));
			}
		}
	}
}
int main(void) {
	// 입출력 시간 단축용
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m, a, b;
	cin >> n >> m;
	for (int i = 0;i < m;i++) {
		int start, end, cost;
		cin >> start >> end >> cost;
		adjs[start].push_back(make_pair(end, cost));
	}
	cin >> a >> b;
	fill(&min_dist[0], &min_dist[1002], INF);
	Dijkstra(a);
	cout << min_dist[b] << endl;
	return 0;
}

결과