[백준 6059] Pasture Walking (C++)

문제 링크: www.acmicpc.net/problem/6059

6059번: Pasture Walking

1. 주의할 점

- LCA문제라고 적혀있지만, N<=1000이므로 플로이드와샬 알고리즘을 사용해도 해결이 가능하다

 

2. 구현

- Arr[][] 배열을 초기화 시킨 후, 각 간선에 대한 정보를 담는다

- 플로이드 와샬 알고리즘을 통해 A↔B 사이의 모든 최단거리를 구해놓는다

- 입력받은 쿼리에 대한 값을 출력한다

#define MAX 987654321
#include <iostream>
using namespace std;
int arr[1001][1001];
int node,query,a,b,val;

void floyd(){
    for(int k=1;k<=node;k++)
        for(int i=1;i<=node;i++)
            for(int j=1;j<=node;j++)
                if(arr[i][j]>arr[i][k]+arr[k][j])
                    arr[i][j]=arr[i][k]+arr[k][j];
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>node>>query;
    for(int i=1;i<=node;i++)
        for(int j=1;j<=node;j++){
            if(i!=j)
                arr[i][j]=MAX;
        }
    for(int i=0;i<node-1;i++){
        cin>>a>>b>>val;
        arr[a][b]=val;
        arr[b][a]=val;
    }
    floyd();
    for(int i=0;i<query;i++){
        cin>>a>>b;
        cout<<arr[a][b]<<'\n';
    }
    return 0;
}