플로이드 와샬 알고리즘으로 푸는 문제이다.
다만 사이클을 어떻게 체크하느냐가 중요할텐데 간단하게 생각해서
arr[i][i]가 INF가 아닌 양수이면 i -> k .. -> i인 루트가 있다는 뜻이므로 arr[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
|
#include<cstdio>
#define INF 1000000000
int arr[402][402];
int v,e,from,to,weight,temp=INF;
int main(void){
scanf("%d %d", &v, &e);
// 초기화
for(int i=1; i<=v; i++)
for(int j=1; j<=v; j++)
arr[i][j]=INF;
// 입력받기 -> 일반통행
for(int i=0; i<e; i++){
scanf("%d %d %d", &from, &to, &weight);
arr[from][to]=weight;
}
// 플로이드 와샬 알고리즘 (사이클까지 계산함)
for(int k=1; k<=v; k++){
for(int i=1; i<=v; i++){
for(int j=1; j<=v; j++){
if(arr[i][j]>arr[i][k]+arr[k][j])
arr[i][j]=arr[i][k]+arr[k][j];
}
}
}
// 사이클 최소값
for(int i=1; i<=v; i++){
if(arr[i][i]<temp){
temp=arr[i][i];
}
}
if(temp==INF) printf("-1");
else printf("%d", temp);
return 0;
}
|
cs |
- Java
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main{
static int INF = 987654321;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine(), " ");
int v = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int[][] arr = new int[v+1][v+1];
for(int i=1; i<=v; i++){
for(int j=1; j<=v; j++)
arr[i][j] = INF;
}
int from=0, to=0, cost=0;
for(int i=0; i<e; i++){
st = new StringTokenizer(br.readLine(), " ");
from = Integer.parseInt(st.nextToken());
to = Integer.parseInt(st.nextToken());
cost = Integer.parseInt(st.nextToken());
arr[from][to] = cost;
}
for(int k=1; k<=v; k++){
for(int i=1; i<=v; i++){
for(int j=1; j<=v; j++){
arr[i][j] = Math.min(arr[i][j], arr[i][k]+arr[k][j]);
}
}
}
int ans = INF;
for(int i=1; i<=v; i++){
if(ans > arr[i][i])
ans = arr[i][i];
}
if(ans == INF) System.out.println("-1");
else System.out.println(ans);
}
}
|
cs |
'백준 2 > 그래프' 카테고리의 다른 글
| [백준 2589] 보물섬 (0) | 2020.12.08 |
|---|---|
| [백준 10159] 저울 (0) | 2020.12.08 |
| [백준 1613] 역사 (C++/Java) (0) | 2020.12.08 |
| [백준 2660] 회장 뽑기 (0) | 2020.12.08 |
| [백준 1389] 케빈 베이컨의 6단계 법칙 (0) | 2020.12.08 |