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

문제 출처: https://www.acmicpc.net/problem/1240

 

 

1. 입력

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

: 그 다음 줄에는 거리를 알고 싶은 M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다.

 

 

2. 결과

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

 

 

3. 풀이

: 노드사이의 최단 거리를 찾는 문제로 플로이드 와샬 알고리즘을 적용할 수 있다.

: 배열을 생성한 후 노드사이의 거리를 입력받는다.

: 서로 연결되지 않은 노드의 거리를 큰 수로 바꿔준다.

: 중간지점을 연결해가며 최단 거리를 구한다.

 

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	static final int INF = 99999999;
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[][] arr = new int[N+1][N+1];
		
		
		for(int i = 0, len = N-1; i < len; i++) {
			st = new StringTokenizer(br.readLine());
			int node1 = Integer.parseInt(st.nextToken());
			int node2 = Integer.parseInt(st.nextToken());
			int dist = Integer.parseInt(st.nextToken());
			arr[node1][node2] = dist;
			arr[node2][node1] = dist;
		}
		
		for(int i = 1; i < N+1; i++) {
			for(int j = 1; j < N+1; j++) {
				if(i != j && arr[i][j] == 0) {
					arr[i][j] = INF;
				}
			}
		}
		
		for(int k = 1; k < N+1; k++) {
			for(int i = 1; i < N+1; i++ ) {
				if(i == k) continue;
				for(int j = 1; j < N+1; j++) {
					if(i != j && k != j) {
						arr[i][j] = Math.min(arr[i][j], arr[i][k] + arr[k][j]); 
					}
				}
			}
		}
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int node1 = Integer.parseInt(st.nextToken());
			int node2 = Integer.parseInt(st.nextToken());
			sb.append(arr[node1][node2]).append("\n");
		}
		
		System.out.println(sb);
	}

}