플로이드

문제

11404번: 플로이드

문제 설명

n(2 ≤ n ≤ 100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1 ≤ m ≤ 100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다.

모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오.

제한 사항

첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.

입출력 예

입력	출력
5
14
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1	0 2 3 1 4
4 5 3	12 0 15 2 5
3 5 10	8 5 0 1 1
3 1 8	10 7 13 0 3
1 4 2	7 4 10 6 0
5 1 7
3 4 2
5 2 4

아이디어

플로이드 와샬 알고리즘 → 노드를 거쳐 간다면 최단 거리 업데이트하는 형식

저번에는 이중 배열로 하고 이번에는 리스트로 했는데 나쁘지 않네

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.List;

// https://www.acmicpc.net/problem/11404
public class four11404 {
    private static int cityCount;
    private static int busCount;
    private static List<List<int[]>> bus;
    private static boolean[][] visited;
    private static int[][] distance;
    public void solution() throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        cityCount = Integer.parseInt(reader.readLine());
        busCount = Integer.parseInt(reader.readLine());
        bus = new ArrayList<>();
        distance = new int[cityCount][cityCount];
        visited = new boolean[cityCount][cityCount];

        for (int i = 0; i < cityCount; i++) {
            bus.add(new ArrayList<>());
        }

        for (int i = 0; i < busCount; i++) {
            StringTokenizer busToken = new StringTokenizer(reader.readLine());
            int startCity = Integer.parseInt(busToken.nextToken()) - 1;
            int endCity = Integer.parseInt(busToken.nextToken()) - 1;
            int cost = Integer.parseInt(busToken.nextToken());
            bus.get(startCity).add(new int[] {endCity, cost});
        }

        for (int[] row : distance) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        for (int i = 0; i < cityCount; i++) {
            distance[i][i] = 0;
        }

        for (int start = 0; start < cityCount; start++) {
            for (int i = 0; i < cityCount; i++) {
                if (start == i) continue;
                int minDist = Integer.MAX_VALUE;
                int minDistCity = -1;
                for (int j = 0; j < cityCount; j++) {
                    if (!visited[start][j] && distance[start][j] < minDist) {
                        minDist = distance[start][j];
                        minDistCity = j;
                    }
                }
                if (minDistCity == -1) break;
                visited[start][minDistCity] = true;

                for (int[] busRow : bus.get(minDistCity)) {
                    int endCity = busRow[0];
                    int cost = busRow[1];
                    if (distance[start][endCity] > distance[start][minDistCity] + cost) {
                        distance[start][endCity] = distance[start][minDistCity] + cost;
                    }
                }
            }
        }
        StringBuilder sb = new StringBuilder();

        for (int[] row : distance) {
            for (int result : row) {
                if (result == Integer.MAX_VALUE) sb.append(0);
                else sb.append(result);
                sb.append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);

        reader.close();
    }

    public static void main(String[] args) throws IOException {
        new four11404().solution();
    }
}