[BOJ/백준][Gold5] 15971 : 두 로봇 (C++)

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

15971번: 두 로봇

 

 

[난이도] Gold5
[유형] DFS

[풀이]
두 로봇 중 한 로봇의 시작점에서 DFS를 시작하여 다른 로봇에 도착할 때까지
지나는 엣지들의 합 total과 엣지중의 최댓값 val을 갱신해줍니다.
다른 로봇에 도착했을 때까지 갱신된 total-val이 정답입니다.

 

 

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N,s,e,ans;
vector<pair<int,int>> adj[100001];
void sol(int n,int prev,int val,int total){
    if(n==e){
        ans=total-val;
        return;
    }
    for(auto [nxt,d] : adj[n]){
        if(nxt!=prev) {
            sol(nxt,n,max(val,d),total+d);
        }
    }
}
int main(){
    scanf("%d%d%d",&N,&s,&e);
    for(int i=0;i<N-1;i++){
        int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        adj[u].push_back({v,d});
        adj[v].push_back({u,d});
    }
    sol(s,0,0,0);
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/15971.cpp