[boj : 15971] 두 로봇

www.acmicpc.net/problem/15971

15971번: 두 로봇

문제 : 두 로봇이 있고 같은 통로에 존재하도록 할때 소요되는 거리의 최소값을 구해라

 

해설 : n개의 정점이 주어지고 n-1개의 간선이 주어질때 무조건 '트리'라는 것을 파악할 수 있어야 된다.

어쨌건 두 로봇은 무조건 같은 통로에 있어야 하니 둘 사이에는 간선이 1개만 존재해야한다. 이는 x->y까지 가는 경로중에 가장 가중치가 높은 간선 1개만 빼주면 된다는 뜻.

 

정점을 하나씩 탐색해주고 목표(y)에 도달하면 return 시켜 역추적해주며 간선의 가중치들을 더해주자.

그 중 가장 큰 값 하나를 빼주면 된다.

 

#include<bits/stdc++.h>

using namespace std;

int n, x, y;
vector<pair<int,int>> v[100001];
int ans,m;

int dfs(int c, int p);

int main()
{	
	cin >> n >> x >> y;
	int a, b, c;
	for (int i = 0; i < n - 1; i++) {
		cin >> a >> b >> c;
		v[a].push_back({ b,c });
		v[b].push_back({ a,c });
	}
	dfs(x,-1);	
	cout << ans-m;
	return 0;
}
int dfs(int c,int p)
{
	if (c == y) 
		return 1;	
	for (pair<int, int> u : v[c])
		if (p != u.first)
			if (dfs(u.first, c)) {
				ans += u.second;
				m = max(m, u.second);
				return 1;
			}
	return 0;
}