녕의 학습 기록
백준_11404 플로이드 (플로이드-워셜) 본문
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BJ_11404_플로이드 {
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());
int[][] distance = new int[n+1][n+1];
int i, j;
for (i=1; i<n+1; i++) {
for (j=1; j<n+1; j++) {
if (i==j) {
distance[i][j] = 0;
} else {
distance[i][j] = 10000001;
}
}
}
StringTokenizer st;
int a, b, c;
for (i=0; i<m; i++) {
st = new StringTokenizer(br.readLine(), " ");
a = Integer.parseInt(st.nextToken());
b = Integer.parseInt(st.nextToken());
c = Integer.parseInt(st.nextToken());
if (distance[a][b] > c) { // 노선 동일하고 가중치가 다른 버스 존재
distance[a][b] = c;
}
}
int k;
for (k=1; k<n+1; k++) {
for (i=1; i<n+1; i++) {
for (j=1; j<n+1; j++) {
distance[i][j] = Math.min(distance[i][j], distance[i][k] + distance[k][j]);
}
}
}
StringBuilder sb = new StringBuilder();
for (i=1; i<n+1; i++) {
for (j=1; j<n+1; j++) {
if (distance[i][j] == 10000001) {
sb.append(0).append(' ');
}else {
sb.append(distance[i][j]).append(' ');
}
}
sb.append('\n');
}
System.out.println(sb);
}
}
11404번: 플로이드
첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가
www.acmicpc.net
'Algorithm > Algorithm 문제' 카테고리의 다른 글
백준_1389 케빈 베이컨의 6단계 법칙 (플로이드-워셜) (1) | 2024.02.29 |
---|---|
백준_11403 경로 찾기 (플로이드-워셜) (1) | 2024.02.28 |
백준_1219 오민식의 고민 (벨만-포드) (1) | 2024.02.26 |
백준_11657 타임머신 (벨만-포드) (0) | 2024.02.25 |
백준_1854 k번째 최단경로 찾기 (다익스트라) (0) | 2024.02.24 |