백준15971 두 로봇

작성일 | In

문제 링크

  • http://icpc.me/15971

문제 출처

  • 2018 KOI 전국 본선 초등부3, 중등부2

사용 알고리즘

  • DFS

시간복잡도

  • O(n)

풀이

중등 2번에 맞지 않는 너무 쉬운 문제라고 생각합니다.

트리 형태로 입력이 주어지고, 두 로봇 사이에 있는 간선의 수를 1 이하가 되게 이동을 시켜야 합니다. 또한 비용은 최소가 되어야 합니다.
동굴이 트리 형태이기 때문에 두 로봇이 각각 a, b에 있다면 a에서 b로 가는 경로는 유일합니다.
정답은 경로 길이에서 가장 긴 간선의 길이를 빼주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> p;
vector<p> g[101010];

int dist[101010];
int maxi[101010];
int chk[101010];

void dfs(int v, int d, int m){
	dist[v] = d;
	maxi[v] = m;
	chk[v] = 1;
	for(auto i : g[v]){
		if(!chk[i.first]) dfs(i.first, d + i.second, max(m, i.second));
	}
}

int main(){
	int n, a, b; cin >> n >> a >> b;
	for(int i=0; i<n-1; i++){
		int s, e, x; cin >> s >> e >> x;
		g[s].push_back({e, x});
		g[e].push_back({s, x});
	}
	if(a == b){
		cout << "0"; return 0;
	}
	dfs(a, 0, 0);
	cout << dist[b] - maxi[b];
}