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

문제링크:https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

 

1753번 문제와 똑같습니다. 한 정점에서의 최단경로를 구하기 위해서 다익스트라를 구현해야 합니다.  

다익스트라를 구현할때 우선순위 큐를 사용해야 합니다. 

min-heap을 이용해서 가장 작은 경로값 부터 적용해주며 진행하여야 컴팩트하게 구현할 수 있습니다.(일반 큐를 사용하면 틀립니다.)

 

 

정답코드입니다.

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;


int a = 0, b = 0; // 출발지, 도착지
int n = 0; // 도시의 개수
int m = 0; // 버스의 개수

vector <int> result;
vector <pair<int, int>> m_arr[1001];

void soultion(int start_index) {

	for (int i = 0; i <= n; i++)
		result.push_back(1000000000); // 최대 값으로 초기화

	priority_queue <pair <int, int >> que; //우선 순위 큐 생성
	que.push(make_pair(0,start_index));

	while (que.empty() == 0) {
		int cost = - que.top().first;
		int destination = que.top().second;
		que.pop();

		if (result[destination] < cost) continue; // 기존 경로가 더 가까우면 continue

		for (int i = 0; i < m_arr[destination].size(); i++) {
			int adjacent_cost =  m_arr[destination][i].second ;
			int adjacent_des = m_arr[destination][i].first;

			if (result[adjacent_des] > adjacent_cost + cost ) {
				result[adjacent_des] = adjacent_cost;
				que.push(make_pair(-result[adjacent_des], adjacent_des));
			}
		}

	}

}

int main(){
	cin >> n;
	cin >> m;
	int u, l, k;
	for (int i = 0; i < m; i++) {
		cin >> u >> l >> k;
		m_arr[u].push_back(make_pair(l, k)); // 
	}
	cin >> a >> b;

	soultion(a);

	cout << result[b] << endl;

	return 0;
}

https://gusdnr69.tistory.com/134?category=799066

[백준] 1753-최단경로

위 문제도 참고하세요.