<백준> 1240

노드사이의 거리

문제
$N$개의 노드로 이루어진 트리가 주어지고 M개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

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

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

입력 받은 두 노드의 거리를 더하면서 탐색하면 되므로 dfs를 사용해줬다.

int n, m;
vector<pair<int, int>> graph[1001];
int visited[1001];

int result;

void dfs(int a, int b, int dist)
{
	visited[a] = 1;

	if (a == b)
	{
		result = dist;
		return;
	}

	for (int i = 0; i < graph[a].size(); i++)
	{
		int cost = dist + graph[a][i].second;
		int node = graph[a][i].first;
		if (visited[node] == 1)
			continue;
		visited[node] = 1;
		dfs(graph[a][i].first, b, cost);
	}
}

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

	for (int i = 0; i < n - 1; i++)
	{
		int x, y, dist;
		cin >> x >> y >> dist;
		graph[x].push_back({ y, dist });
		graph[y].push_back({ x,dist });
	}

	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		dfs(a, b, 0);
		memset(visited, 0, sizeof(visited));
		cout <<result << '\n';
	}
}