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

1240번: 노드사이의 거리

---

---

---

• 제목

노드사이의 거리

---

• 조건

시간 제한 : 2 초

메모리 제한 : 512 MB 

---

• 문제

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

---

• 입력

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

---

• 출력

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

---

예제 입력 1	예제 출력 1
4 2 2 1 2 4 3 2 1 4 3 1 2 3 2	2 7

---

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
vector<pair<int, int>> node[1001];
int N, M;
bool visited[1001];
int dist[1001];
void initialize() {
	for (int n = 1; n <= N; n++) {
		visited[n] = false;
		dist[n] = 0;
	}
}
void BFS(int start, int end) {
	initialize();
	queue<int> que;
	que.push(start);
	visited[start] = true;
	while (!que.empty()) {
		int curr = que.front();
		int currW = dist[curr];
		que.pop();

		for (int n = 0; n < node[curr].size(); n++) {
			int next = node[curr][n].first;
			int nextW = node[curr][n].second;
			if (visited[next]) continue;
			dist[next] = currW + nextW;
			visited[next] = true;
			que.push(next);
		}
	}
	cout << dist[end] << endl;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int from, to, weight;
	cin >> N >> M;
	for (int n = 0; n < N - 1; n++) {
		cin >> from >> to >> weight;
		node[from].push_back(make_pair(to, weight));
		node[to].push_back(make_pair(from, weight));
	}
	for (int n = 0; n < M; n++) {
		cin >> from >> to;
		BFS(from, to);
	}
	return 0;
}