Programming/백준
[백준] 11404번 : 플로이드
조용한고라니
2021. 2. 27. 18:24
반응형
11404번: 플로이드
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가
www.acmicpc.net
기본적인 플로이드-와샬 알고리즘 문제. 플로이드 와샬의 응용이 아니므로 간단하게 풀 수 있다.
static void Floyd(int n){
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(i == j) continue;
else
d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++)
System.out.print(d[i][j] != INF? d[i][j] + " " : 0 + " ");
System.out.println();
}
}# Code </>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static final int INF = 1000000000;
static int[][] d = new int[101][101];
static void Floyd(int n){
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
if(i == j) continue;
else d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++)
System.out.print(d[i][j] != INF? d[i][j] + " " : 0 + " ");
System.out.println();
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int m = Integer.parseInt(br.readLine());
for(int i=1; i<=n; i++)
Arrays.fill(d[i], INF);
for(int i=0; i<m; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
int depart = Integer.parseInt(st.nextToken());
int arrive = Integer.parseInt(st.nextToken());
int distance = Integer.parseInt(st.nextToken());
d[depart][arrive] = Math.min(d[depart][arrive], distance);
}
Floyd(n);
}
}반응형