15971 두 로봇

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

두 로봇의 위치 사이의 거리에서 가장 큰 비용의 간선을 빼주면 된다. 그러면 최소 비용으로 양쪽에서 오다가 서로 만날 수 있다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int n,s,e,u,v,w,c[100001],ans,f;
vector<pair<int,int>> a[100001];
 
void dfs(int now,int cost,int mcost)
{
    c[now]=true;
    if(f) return;
    if(now==e)
    {
        f=1;
        ans=cost-mcost;
        return;
    }
    for(auto i : a[now])
    {
        int next=i.first;
        int ncost=i.second;
        if(c[next]==false)
            dfs(next,cost+ncost,max(mcost,ncost));
    }
}
 
int main()
{
    scanf("%d %d %d",&n,&s,&e);
    for(int i=0;i<n-1;i++)
    {
        scanf("%d %d %d",&u,&v,&w);
        a[u].push_back({v,w});
        a[v].push_back({u,w});
    }
    dfs(s,0,0);
    printf("%d\n",ans);
    return 0;
}