[BOJ 1240] 노드사이의 거리

[ 접근법 ]

1. 거리를 계산하기 때문에, 거리를 저장할 2차원 배열을 만든다.

2. 다른 조건이 없으므로, 자식들을 DFS로 돌면서 자신과 목표가 같을 때 거리를 출력한다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define MAX 1001

vector<int> v[MAX];
bool visited[MAX];
int parent[MAX];
int lenth[MAX][MAX];

void init() {
	for (int i = 1; i < MAX; i++) {
		visited[i] = false;
	}
}

void dfs(int start, int end, int len, int before) {
	visited[start] = true;
	
	if (start == end) {
		cout << len << endl;
		return;
	}

	for (int i = 0; i < v[start].size(); i++) {
		int child = v[start][i];
		if (child == before)	continue;
		if (!visited[child]) {
			dfs(child, end, len + lenth[start][child], start);
		}
		
	}
}

int main() {
	int N, M;
	cin >> N >> M;
	N--;
	while (N--) {
		
		int a=0, b=0, len=0;
		cin >> a >> b >> len;
		
		v[a].push_back(b);
		v[b].push_back(a);
		lenth[a][b] = len;
		lenth[b][a] = len;
	}
	while (M--) {
		init();
		int start, end;
		int res = 0;
		cin >> start >> end;
		dfs(start, end, 0, 0);
	}
}