[JAVA 07] 11723.플로이드

11723. 플로이드 (G4)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	74987	32289	22712	42.111 %

 

문제

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

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

입력

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

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

출력

n개의 줄을 출력해야 한다. i번째 줄에 출력하는 j번째 숫자는 도시 i에서 j로 가는데 필요한 최소 비용이다. 만약, i에서 j로 갈 수 없는 경우에는 그 자리에 0을 출력한다.

 

 

 

---

summary

도시 A에서 B로 가는데 필요한 비용의 최솟값

 

strategy

플로이드-워셜 알고리즘 사용 (모든 지점에서 다른 모든 지점으로 최단 경로)

 

 

note

- n(2 ≤ n ≤ 100)

- m(1 ≤ m ≤ 100,000)

- 비용은 100,000보다 작거나 같은 자연수 (INF = 10,000 * 100) 

 

 

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

public class Main {

    static int N, M;
    static int[][] map;
    static final int INF = 100000 * 100;
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder answer = new StringBuilder();

        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) map[i][j] = INF;
            }
        }
        
        for(int m = 0; m < M; m++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int i = Integer.parseInt(st.nextToken());
            int j = Integer.parseInt(st.nextToken());
            map[i][j] = Math.min(Integer.parseInt(st.nextToken()), map[i][j]);
        }

       for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (map[i][j] > map[i][k] + map[k][j]) {
                        map[i][j] = map[i][k] + map[k][j];
                    }
                }
            }
        }

        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                if(map[i][j] == INF) map[i][j] = 0;
                
                answer.append(map[i][j]).append(" ");
            }
            answer.append("\n");
        }
        System.out.println(answer);
    }
}

 

문제	결과	메모리	시간	언어코드	길이
11404	맞았습니다!!	43648	364 ms	Java 11 / 수정	1566

 

MEMO

- 경로가 아닌 최소 비용을 묻고 있다.

- 한 경로가 아닌 모든 지역에 대한 비용을 묻고 있다.

- 그래프 이론 중 플로이드-워셜 을 알고있으면 쉽게 풀 수 있다.