문제
풀이
플로이드-와샬 : O(N^3) 알고리즘을 이용한 문제이다. 역추적을 위해서 경유지인 k를 저장해놓고, 그 start와 k, 그리고 k와 end들의 경유지를 찾아내는 재귀함수꼴로 역추적을 진행한다. 예를 들어, 2에서 3으로 갈 때, 경유지 5를 지난다면 2에서 5로 갈 때 경유지가 있는지 체크, 5에서 3으로 갈 때 경유지가 있는지 체크하는 식의 재귀함수를 말한다. 출력은 route[i][j] == 0일 때, start와 end를 출력하면 그 경로가 완성되며, 경유지가 두번 출력이 되므로, 경유지를 한번 지우고 출력하는 식으로 진행한다.
소스 코드
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
85
86
87
#include <iostream>
#include <vector>
#define INF 987654321
using namespace std;
int n, m;
int dp[101][101];
int route[101][101];
vector<int> answer;
void find_route(int start, int end){
if(route[start][end] == 0){
answer.push_back(start);
answer.push_back(end);
return;
}
else{
int k = route[start][end];
find_route(start, k);
answer.pop_back();
find_route(k, end);
}
}
void Floyd_warshall(){
for(int k = 1; k<=n; k++){
for(int i = 1; i<=n; i++){
for(int j = 1; j<=n; j++){
if(i==j) continue;
if(dp[i][k] + dp[k][j] < dp[i][j]){
dp[i][j] = dp[i][k] + dp[k][j];
route[i][j] = k;
}
}
}
}
for(int i = 1; i<= n; i++){
for(int j = 1; j<=n; j++){
if(dp[i][j] == INF) printf("0 ");
else printf("%d ", dp[i][j]);
}
printf("\n");
}
for(int i = 1; i<=n; i++){
for(int j = 1; j<=n; j++){
if(dp[i][j] == INF){
printf("0\n");
continue;
}
else{
answer.clear();
find_route(i, j);
printf("%d ", (int)answer.size());
for(int i = 0; i<answer.size(); i++){
printf("%d ", answer[i]);
}
}
printf("\n");
}
}
}
int main(){
scanf("%d", &n);
scanf("%d", &m);
for(int i = 1; i <= n; i++){
for(int j = 1; j<= n; j++){
dp[i][j] = INF;
}
}
for(int i = 0; i<m; i++){
int from, to, value;
scanf("%d %d %d", &from, &to, &value);
dp[from][to] = min(dp[from][to], value);
}
Floyd_warshall();
return 0;
}
