P.11404 플로이드

코드

import java.io.*;
import java.util.Arrays;

public class P_11404 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());
        long[][] cities = new long[n + 1][n + 1];
        for (int i = 1; i <= n; i++) Arrays.fill(cities[i], Integer.MAX_VALUE);
        for (int i = 0 ; i < m; i++) {
            int[] s = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            if (cities[s[0]][s[1]] > s[2]) cities[s[0]][s[1]] = s[2];
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j<= n; j++) {
                for (int k = 1; k <= n; k++) {
                    if (j == k) cities[j][k] = 0;
                    else if (cities[j][k] > cities[j][i] + cities[i][k]) cities[j][k] = cities[j][i] + cities[i][k];
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j<= n; j++) {
                if (cities[i][j] == Integer.MAX_VALUE) cities[i][j] = 0;
                bw.write(cities[i][j] + " ");
            }
            bw.newLine();
        }
        bw.flush();
    }
}

코드 설명

플로이드 워셜 알고리즘을 사용하면 된다.

주의할 점은 s정점에서 e정점으로 이동할 수 있는 버스의 수가 여러 대일 수 있는데 입력 시 비교를 하여 가장 짧은 것을 받아야 한다.