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

문제

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

입력

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

출력

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

예제 입력 1

4 2
2 1 2
4 3 2
1 4 3
1 2
3 2

예제 출력 1

2
7

풀이

이 문제는 다익스트라 알고리즘을 이용해서 간단하게 풀 수 있는 문제였다.

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

public class Main {

    static int N;
    static long[][] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        N = Integer.parseInt(str[0]);
        int M = Integer.parseInt(str[1]);
        graph = new long[N+1][N+1];

        for(int i=0; i<N-1; i++) {
            String[] input = br.readLine().split(" ");
            int start = Integer.parseInt(input[0]);
            int end = Integer.parseInt(input[1]);
            long cost = Long.parseLong(input[2]);

            graph[start][end] = cost;
            graph[end][start] = cost;
        }

        for(int i=0; i<M; i++) {
            String[] input = br.readLine().split(" ");
            int start = Integer.parseInt(input[0]);
            int end = Integer.parseInt(input[1]);
            long[] length = dijkstra(start);
            System.out.println(length[end]);
        }
    }


    static long[] dijkstra(int v){
        long distance[] = new long[N+1];
        boolean[] check = new boolean[N+1];

        for(int i=1;i<N+1;i++){
            distance[i] = Long.MAX_VALUE;
        }

        distance[v] = 0;
        check[v] = true;

        for(int i=1;i<N+1;i++){
            if(!check[i] && graph[v][i]!=0){
                distance[i] = graph[v][i];
            }
        }

        for(int a=0;a<N-1;a++){
            long min=Long.MAX_VALUE;
            int min_index=-1;

            for(int i=1;i<N+1;i++){
                if(!check[i] && distance[i]!=Long.MAX_VALUE){
                    if(distance[i]<min ){
                        min=distance[i];
                        min_index = i;
                    }
                }
            }

            check[min_index] = true;

            for(int i=1;i<N+1;i++){
                if(!check[i] && graph[min_index][i]!=0){
                    if(distance[i]>distance[min_index]+graph[min_index][i]){
                        distance[i] = distance[min_index]+graph[min_index][i];
                    }
                }
            }
        }

        return distance;
    }
}