Coding - Algo/Java
[백준] 1956번:운동 (Java 자바)
jainn
2021. 9. 18. 20:06
728x90
문제
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
풀이 및 소스코드
플로이드 와샬 알고리즘으로 푸는 문제이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
class Main {
public static void main(String[] args) throws NumberFormatException, 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[][] dp = new int[v][v];
for (int i = 0; i < v; i++) {
Arrays.fill(dp[i], 10001);
}
for (int i = 0; i < e; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken())-1;
int b = Integer.parseInt(st.nextToken())-1;
int c = Integer.parseInt(st.nextToken());
dp[a][b] = c;
}
for (int k = 0; k < v; k++) {
for (int i = 0; i < v; i++) {
for (int j = 0; j < v; j++) {
dp[i][j] = Math.min(dp[i][k] + dp[k][j], dp[i][j]);
}
}
}
int res = Integer.MAX_VALUE;
for (int i = 0; i < v; i++) {
if (res > dp[i][i]) {
res = dp[i][i];
}
}
if (res == 10001) {
System.out.println("-1");
} else {
System.out.println(res);
}
}
}
반응형