Baekjoon 1956, 백준 1956 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제보기
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
| #include <cstdio>
#include <algorithm>
#define INF 999999999
using namespace std;
int V, E;
int dp[402][402];
void Floyd_Warshall() {
for(int temp = 1; temp <= V; temp++){
for(int i = 1; i <= V; i++){
for(int j = 1; j <= V; j++){
if(dp[i][temp] != INF && dp[temp][j] != INF){
dp[i][j] = min(dp[i][j], dp[i][temp] + dp[temp][j]);
}
}
}
}
}
int main() {
scanf("%d %d", &V, &E);
for(int i = 1; i <= V; i++){
for(int j = 1; j <= V; j++){
if(i == j) dp[i][j] = 0;
else dp[i][j] = INF;
}
}
while(E--){
int from, to, value;
scanf("%d %d %d", &from, &to, &value);
if(dp[from][to] > value)
dp[from][to] = value;
}
Floyd_Warshall();
int ans = INF;
for(int i = 1; i <= V; i++){
for(int j = 1; j <= V; j++){
if(i != j) ans = min(ans, dp[i][j] + dp[j][i]);
}
}
if(ans == INF)
printf("-1\n");
else printf("%d\n", ans);
}
|
어떠한 최단 경로 알고리즘을 쓸까 고민하던 중, ASP 중 하나인 플로이드 워셜 알고리즘 ( Floyd-Warshall Algorithm) 을 사용하여 문제를 해결하였다.
평범하게 플로이드 워셜을 모든 출발점과 도착점에 대해 진행해준 후, dp[start][end] + dp[end][start] 의 최솟값을 찾아주면 끝이었다.
