[BaekJoon] 백준 1240. 노드사이의 거리

https://www.acmicpc.net/problem/1240

[1240번: 노드사이의 거리

N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

www.acmicpc.net](https://www.acmicpc.net/problem/1240)

---

문제

N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

입력

첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리(10,000 이하의 정수)를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다.

출력

M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다.

---

풀이 :

플로이드 와샬을 사용하면 쉽게 구할 수 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        int INF = 98765432;
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] tmp = reader.readLine().split(" ");
        int N = Integer.parseInt(tmp[0]);
        int M = Integer.parseInt(tmp[1]);
        int[][] dist = new int[N+1][N+1];

        for(int i = 1; i<=N; i++) {
            Arrays.fill(dist[i], INF);
        }

        for(int i = 0; i<N-1; i++) {
            String[] input = reader.readLine().split(" ");
            int x = Integer.parseInt(input[0]);
            int y = Integer.parseInt(input[1]);
            int d = Integer.parseInt(input[2]);

            dist[x][y] = d; dist[y][x] = d;
        }

        for(int i = 1; i<=N; i++) {
            for(int j = 1; j<=N; j++) {
                for(int k = 1; k<=N; k++) {
                    dist[j][k] = Math.min(dist[j][k], dist[j][i] + dist[i][k]);
                }
            }
        }

        for(int i = 0; i<M; i++) {
            String[] input = reader.readLine().split(" ");
            System.out.println(dist[Integer.parseInt(input[0])][Integer.parseInt(input[1])]);
        }
    }
}