알고리즘/다익스트라
다익스트라 - 최소 비용 구하기
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];
}
}