[BOJ 1240][c++] 노드사이의 거리

 

https://www.acmicpc.net/problem/1240

1240번: 노드사이의 거리

 

dfs,bfs문제이다. 루트로부터 각 노드까지의 거리를 구하고, 공통 부분을 빼주면 된다.

 

코드는 아래에 있다.

#include<bits/stdc++.h>
using namespace std;

vector<pair<int,int>> g[1001];

bool c(pair<int,int> a,pair<int,int> b){return a.first<b.first;}
bool v[1001];

int p[1001];
int h[1001];
int t[1001];

void d(int s,int l){
	v[s]=true;
	h[s]=l;
	
	for(int i=0;i<g[s].size();i++){
		int n=g[s][i].first,D=g[s][i].second;
		if(!v[n]){
			p[n]=s;
			t[n]=t[s]+D;
			d(n,l+1);
		}
	}
}

int l(int a,int b){
	while(h[a]!=h[b]){
		if(h[a]>h[b]) a=p[a];
		else b=p[b];
	}
	while(a!=b){
		a=p[a];
		b=p[b];
	}
	return a;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n,m;
	cin >> n >> m;
	
	for(int i=1;i<n;i++){
		int f,t,c;
		cin >> f >> t >> c;
		
		g[f].push_back(make_pair(t,c));
		g[t].push_back(make_pair(f,c));
	}
	
	for(int i=1;i<=n;i++){
		sort(g[i].begin(),g[i].end(),c);
	}
	
	d(1,0);
	
	for(int i=0;i<m;i++){
		int x,y;
		cin >> x >> y;
		int g=l(x,y);
		
		if(g==1) cout << t[x]+t[y] << '\n';
		else cout << t[x]+t[y]-t[g]*2 << '\n';
	}
	
	return 0;
}