알고리즘/다익스트라

다익스트라 - 최소 비용 구하기

sim0609 2023. 7. 15. 13:52

<문제>

백준 - 1916: 최소 비용 구하기

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

 

1916번: 최소비용 구하기

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그

www.acmicpc.net

 

<문제 접근>

이전 글의 최단 경로 구하는 방식과 동일하게 우선순위 큐를 통해 최단 경로를 비교해 업데이트하고 최종 정답 배열에 저장하는 방식으로 구현하면 된다.

 

 

<슈도 코드>

 

 

<코드>

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;

typedef pair<int, int> p;
vector<int> visited;
vector<int> answer;
vector<vector<p>> graph_list; 
priority_queue<p, vector<p>, greater<p>> p_q; // 거리가 동일한 경우, 노드를 비교해 오름차순 정렬

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

	int n, e, start_n, end_n;
	int u, v, w;

	cin >> n;
	cin >> e;

	visited.resize(n + 1);
	answer.resize(n + 1);
	graph_list.resize(n + 1);

	fill(visited.begin(), visited.end(), 0);
	fill(answer.begin(), answer.end(), INT_MAX);

	for (int i = 0; i < e; i++) {
		cin >> u >> v >> w;
		graph_list[u].push_back(make_pair(v, w)); // (노드, 가중치)
	}

	cin >> start_n >> end_n;

	p_q.push(make_pair(0, start_n)); // (거리, 노드)
	answer[start_n] = 0;

	while (!p_q.empty()) {
		p f = p_q.top();
		p_q.pop();
		int f_node = f.second;

		if (visited[f_node] == 1) {
			continue;
		}

		visited[f_node] = 1;

		for (int i = 0; i < graph_list[f_node].size(); i++) {
			int next = graph_list[f_node][i].first;
			if (answer[next] > answer[f_node] + graph_list[f_node][i].second) {
				answer[next] = answer[f_node] + graph_list[f_node][i].second;
				p_q.push(make_pair(answer[next], next));
			}
		}

	}

	if (visited[end_n] == 1) {
		cout << answer[end_n];
	}

}