[BOJ] 백준 15971 두 로봇

문제 링크

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

15971번: 두 로봇

 

두 로봇은 인접한 노드에 있으면 통신이 가능합니다.

 

풀이

1) 두 로봇 사이 최단 거리를 dfs로 구해줍니다.

2) 위에서 구한 최단거리에서, 두 로봇 사이의 경로에 포함된 간선 중 가중치가 가장 큰 간선의 거리를 빼줍니다.

 

풀이를 두 단계로 적어놨지만 사실 dfs 한 번으로 1), 2)를 동시에 구할 수 있습니다.

자세한 내용은 코드를 참고해주세용

 

 

 

정답 코드

	#include <bits/stdc++.h>
	using namespace std;
	using pii = pair<int, int>;
	#define ft first
	#define sd second
	int n, s1, s2;
	struct Edge{
	int to;
	int cost;
	Edge(int t=0, int c=0):to(t), cost(c){}
	};
	vector<vector<Edge>> p;
	bool chk[110'000];
	pii zero = {0, 0};
	pii dfs(int now, pii ret){
	if(chk[now]) return zero;
	chk[now] = true;
	if(now == s2) return ret;
	pii tmp;
	for(auto e: p[now]){
	int next = e.to;
	int ncost = e.cost;
	if((tmp = dfs(next, {ret.ft + ncost, max(ret.sd, ncost)})).ft != 0)
	return tmp;
	}
	return zero;
	}
	int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>s1>>s2;
	p.resize(n+1);
	for(int i=0; i<n-1; i++){
	int u, v, c;
	cin>>u>>v>>c;
	p[u].emplace_back(v, c);
	p[v].emplace_back(u, c);
	}
	pii ans = dfs(s1, zero);
	cout<<ans.ft - ans.sd;
	}

view raw .cpp hosted with ❤ by GitHub