문제링크 : https://www.acmicpc.net/problem/11779
이 문제는 다익스트라 알고리즘을 사용하여 ARRIVE 지점까지의 최단거리를 구한 후, 경로를 출력하는 문제이다.
최단거리를 구하는 것은 다익스트라 알고리즘의 특성으로, 시작점에서 모든 점까지의 최단거리를 찾을 수 있으므로 간단하게 distance[arrive]로 찾을 수 있다.
최단거리의 경로는, 최단거리들이 갱신 될 때 이 점의 부모(이 점에 도달한다고 한다면 이 점 직전의 노드)를 배열에 저장해주면 간단하게 해결 된다.
소스코드 :
이 문제는 다익스트라 알고리즘을 사용하여 ARRIVE 지점까지의 최단거리를 구한 후, 경로를 출력하는 문제이다.
최단거리를 구하는 것은 다익스트라 알고리즘의 특성으로, 시작점에서 모든 점까지의 최단거리를 찾을 수 있으므로 간단하게 distance[arrive]로 찾을 수 있다.
최단거리의 경로는, 최단거리들이 갱신 될 때 이 점의 부모(이 점에 도달한다고 한다면 이 점 직전의 노드)를 배열에 저장해주면 간단하게 해결 된다.
소스코드 :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#define INF 987654321
using namespace std;
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
// v : amount of vertex, e : amount of edges.
int v, e;
cin >> v >> e;
// Priority Queue for managing minimum weight.
priority_queue < pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
// Array for managing distance between node to another.
vector<int> distance(v + 1, INF);
// Entire graph.
vector<vector<pair<int, int> > > graph(v+1);
for (int i = 0; i < e; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back({ v,w });
}
// The starting node's index.
int k, arrive;
cin >> k >> arrive;
pq.push({ 0 , k });
// going back to myself get a value zero.
distance[k] = 0;
vector<int> path(v + 1);
for (int i = 1; i <= v; i++) {
path[i] = i;
}
while (!pq.empty()) {
int node = pq.top().second;
int weight = pq.top().first;
pq.pop();
if (distance[node] < weight)
continue;
for (int i = 0; i < graph[node].size(); i++) {
int neighbor = graph[node][i].first;
int neighborDistance = weight + graph[node][i].second;
if (neighborDistance <= distance[neighbor] ) {
distance[neighbor] = neighborDistance;
pq.push({ distance[neighbor], graph[node][i].first });
path[neighbor] = node;
}
}
}
cout << distance[arrive] << "\n";
int i = arrive;
int cnt = 0;
stack<int> path_output;
while (path[i] != i) {
cnt++;
path_output.push(path[i]);
i = path[i];
}
cout << cnt + 1 << "\n";
while (!path_output.empty()) {
cout << path_output.top() << ' ';
path_output.pop();
}
cout << arrive << endl;
}
| cs |
댓글
댓글 쓰기