문제
풀이
- 다익스트라 알고리즘에 경로 추적을 추가한 문제이다.
- 다익스트라 알고리즘 도중 최단 경로가 갱신되면 노드의 부모 노드를 교체한 방식으로 진행한다.
- next_node에 최단 경로로 도달하기 위해서는 current_node에서 와야 한다.
코드
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
int n, m;
int start_node, end_node;
vector<vector<pair<int, int>>> graph;
int dist[1001][1001];
int parent[1001];
vector<int> path;
void dijkstra(int n)
{
dist[n][n] = 0;
parent[n] = n;
priority_queue<pair<int, int>> pq;
pq.push(make_pair(0, n));
while (!pq.empty())
{
int current_node = pq.top().second;
int current_dist = (-1) * pq.top().first;
pq.pop();
if (current_dist > dist[n][current_node])
{
continue;
}
for (auto next : graph[current_node])
{
int next_node = next.second;
int next_dist = next.first + current_dist;
// 경로 갱신
if (dist[n][next_node] > next_dist)
{
dist[n][next_node] = next_dist;
pq.push(make_pair((-1) * next_dist, next_node));
// 최소비용으로 next_node에 도달하기 위해선 current_node를 바로 이전에 지나야 한다.
parent[next_node] = current_node;
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
fill(&dist[0][0], &dist[1000][1001], INT_MAX);
graph.resize(n + 1);
for (int i = 1; i <= n; ++i)
{
graph[i].resize(n + 1);
}
while (m--)
{
int n1, n2, dist;
cin >> n1 >> n2 >> dist;
graph[n1].push_back(make_pair(dist, n2));
}
cin >> start_node >> end_node;
dijkstra(start_node);
cout << dist[start_node][end_node] << endl;
// 경로 추적
// 현재 노드의 부모 노드를 추적하면서 부모 노드가 start_node일 경우 정지
int current_parent = end_node;
while (current_parent != start_node)
{
path.push_back(current_parent);
current_parent = parent[current_parent];
}
path.push_back(start_node); // 시작 노드 push
cout << path.size() << endl;
for (int i = 0; i < path.size(); ++i)
{
cout << path[path.size() - 1 - i] << " ";
}
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준][C++] 13172: Σ (0) | 2023.10.05 |
---|---|
[백준][C++] 2448: 별 찍기 - 11 (0) | 2023.10.04 |
[백준][C++] 2638: 치즈 (0) | 2023.10.02 |
[백준][C++] 17144: 미세먼지 안녕! (0) | 2023.10.02 |
[백준][C++] 14938: 서강그라운드 (0) | 2023.09.30 |