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

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

1240번: 노드사이의 거리

N개의 노드로 이루어진 트리가 주어진다.

트리로 이루어져 있기 때문에 사이클이 없고 노드와 노드 사이의 길이 하나만 존재함을 알 수 있다.

따라서 거리를 알고 싶은 노드 A에서 BFS를 시작하여 B를 만나는 지점에서 그 거리를 갱신하고 BFS를 종료하여 해결함.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <string>

using namespace std;

typedef pair<int, int>P;

vector<P> adj[1001];
int visited[1001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    int M;
    cin >> N >> M;
    for (int i = 0; i < N-1; i++) {
        int a, b, d;
        cin >> a >> b >> d;
        adj[a].push_back(P(b, d));
        adj[b].push_back(P(a, d));
    }

    for (int i = 0; i < M; i++) {
        fill(&visited[0], &visited[1001], 0);
        queue<P>q;
        int start, end;
        cin >> start >> end;
        q.push(P(start,0));
        visited[start] = 1;

        int min = 123456789;

        while (!q.empty()) {
            P curr = q.front(); q.pop();
            if (curr.first == end) {
                min = curr.second;
                break;
            }

            for (auto next : adj[curr.first]) {
                if (visited[next.first] == 0) {
                    visited[next.first] = 1;
                    q.push(P(next.first, curr.second + next.second));
                }
            }
        }
        cout << min << '\n';
    }

}