문제 URL :https://www.acmicpc.net/problem/1956
1956번: 운동
첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2<=V<=400, 0<=E<=V*(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의미이다.
www.acmicpc.net
문제 접근법 :
문제유형 플로이드 와샬을 이용한 알고리즘이기때문에 플로이드를 사용하신다는 것은 알고계실껍니다
하지만 싸이클을 중에 가장 작은 값을 출력하는문제 입니다. 하지만 싸이클이라는 성질만 잘생각해보면
간단한 문제입니다.
싸이클이라는경우는 어차피 계속적으로 순회하기때문에 자기자신에게 돌아오온다는 성질을 이용하면
map[i][i] 자기자신에서 가는방향도 무한대로 집어넣고 만약 무한대가 아닌경우 사이클이 발생했다는걸 알수있습니다.
그렇기에 자기자신에서 가는 경로중에 가장 작은 값을 찾아 출력하면 되는문제이기때문에
문제핵심만 잘 이해하면 쉽게 풀수있습니다.
|
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
|
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int v, e;
int map[401][401];
void floyd(){
for (int k = 1; k <= v; k++)
{
for (int i = 1; i <= v; i++)
{
for (int j = 1; j <= v; j++)
{
map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
}
}
}
}
int main()
{
cin >> v >> e;
for (int i = 1; i <= v; i++){
for (int j = 1; j <= v; j++){
map[i][j] = 1e+9;
}
}
for (int i = 0; i < e; i++)
{
int x, y, z;
cin >> x >> y >> z;
map[x][y] = z;
}
floyd();//플로이드를 통해 모든최소경로를 구함
int mincycle = 1e+9;
for (int i = 1; i <= v; i++)
{
if (map[i][i] != 1e+9)//자기자신에게 가능 경로가있다면 그것은 싸이클
mincycle = min(mincycle, map[i][i]);
}
if (mincycle == 1e+9)
cout << -1 << "\n";
else
cout << mincycle << "\n";
}
|
cs |
궁금한점 혹은 모르는것이 있다면 언제든지 댓글을 이용해주시길 바랍니다.
'백준' 카테고리의 다른 글
| 백준 10769 행복한지 슬픈지 (0) | 2020.08.10 |
|---|---|
| 백준 16943 숫자 재배치 (0) | 2020.08.07 |
| 백준 11779 최소비용 구하기 2 (0) | 2020.08.07 |
| 백준 2178 미로 탐색 (0) | 2020.08.06 |
| 백준 1822 차집합 (0) | 2020.08.06 |