1956 운동
알고리즘(플로이드 워셜)
1
2
3
4
5
6
7
1. 문제 파악 : 그래프 상의 어떤 점들 집합이건 최소로 사이클을 이루는 집합이면 됨
2. 그래프 관련 알고리즘
1. 다익스트라 : 출발점에서 모든 정점까지의 거리 -> 해당 x
2. 밸만포드 : 다익스트라와 마찬가지
3. MST : 최소신장트리 -> 사이클은 감지할 수 있으나, 그것이 최소 사이클인지 모름 and 사이클만을 추출해내기 어려움
4. 플로이드 워셜 : 모든 정점 사이의 거리
-> 자기 자신은 원래 0으로 표시하지만, 이 문제에선 INF로 한다면 사이클을 감지할 수 있고 또 최소 사이클도 감지하기 쉬움
코드
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
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
long long N, E, edges[401][401];
int floid();
int main() {
cin >> N >> E;
for (int i = 0; i < 401; i++)
for (int j = 0; j < 401; j++)
edges[i][j] = INF;
for (int i = 0; i < E; i++) {
int a, b, c;
cin >> a >> b >> c;
edges[a][b] = c;
}
cout << floid();
}
int floid() {
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
for (int k = 1; k <= N; k++)
if (edges[j][k] > edges[j][i] + edges[i][k])
edges[j][k] = edges[j][i] + edges[i][k];
int result = INF;
for (int i = 1; i <= N; i++)
result = result < edges[i][i] ? result : edges[i][i];
if (result == INF)
return -1;
return result;
}