https://www.acmicpc.net/problem/11404
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
public static final int INF = 100000000;
public static int n, m;
public static int[][] map;
public static void floyd(){
for(int k=1; k<=n; k++){
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
map[i][j] = Math.min(map[i][j], map[i][k]+map[k][j]); // i->k->j 거리와 i->j 거리 비교
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine()); // 도시의 개수
m = Integer.parseInt(br.readLine()); // 버스의 개수
map = new int[n+1][n+1];
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(i==j) continue; // 출발 도시와 도착 도시가 같으면 0
map[i][j] = INF;
}
}
while(m-->0){
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
map[start][end] = Math.min(map[start][end], cost); // 노선이 하나가 아닐 수 있으므로 최솟값으로 갱신
}
floyd();
StringBuilder sb = new StringBuilder();
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(map[i][j] >= INF) sb.append("0 ");
else sb.append(map[i][j]).append(" ");
}
sb.append("\n");
}
System.out.println(sb);
}
}
'ALGORITHM' 카테고리의 다른 글
[JAVA] 백준 11657- 타임머신(벨만 포드) (0) | 2023.01.23 |
---|---|
[JAVA] 백준 1541- 잃어버린 괄호 (0) | 2023.01.21 |
[JAVA] 백준 1202번- 보석 도둑 (0) | 2023.01.16 |
[JAVA] 백준 13305번- 주유소 (0) | 2023.01.13 |
[JAVA] 백준 13549번- 숨바꼭질 3 (0) | 2023.01.09 |