백준 - 두 로봇 : 15971

 

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

15971번: 두 로봇

 

 

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/*
5 1 5
1 2 1
2 3 2
3 4 3
4 5 4
*/
int vi[100010],max1,tot;
vector <pair<int,int>> v[100010];

void dfs(int s, int e, int lmax, int l)
{
    if(s==e) {
        max1=lmax;
        tot=l;
    }
    else{
        vi[s]++;
        for(int i=0;i<v[s].size();i++)
        {
            if(vi[v[s][i].first]==0)
            {
                int last=lmax>v[s][i].second?lmax:v[s][i].second;
                dfs(v[s][i].first,e,last,l+v[s][i].second);
            }
        }
    }

}
int main()
{
    int r,r1,r2,i,s,e,d;

    scanf("%d %d %d",&r,&r1,&r2);
    for(i=1;i<r;i++)
    {
        scanf("%d %d %d",&s,&e,&d);
        v[s].push_back(make_pair(e,d));
        v[e].push_back(make_pair(s,d));
    }
    dfs(r1,r2,0,0);
    printf("%d",tot-max1);
    return 0;
}