15971 - 두 로봇(C++)

풀이

문제의 핵심만 파악하면 쉽게 풀 수 있는 문제였다. 여기서 핵심은 첫 로봇에서 다른 로봇에까지 가는 데 발생하는 cost를 모두 더하여 구한 후 이동하였던 경로 중 가장 큰 cost가 발생하였던 것을 빼주면 답이 나오는 문제였다. 이때 그래프 탐색은 dfs를 활용하여 구현하였으며, 목표한 다른 로봇에 도달하였을 때 flag를 설정하여, dfs 이동 경로 중 발생한 cost를 계산하였다.

 

#include <iostream>
#include<vector>
using namespace std;
int N,t1,t2;
vector<pair<int,int>> g[100001];
bool visited[100001],flag;
int tmp,ans;
void dfs(int v,int u){
    if(v==u){
        flag = true;
        visited[u] = true;
        return;
    }
    visited[v] = true;
    for(int i=0;i<g[v].size();i++){
        int next = g[v][i].first;
        int cost = g[v][i].second;
        if(!visited[next]){
            dfs(next,u);
        }
        if(flag){
            ans += cost;
            tmp = max(tmp,cost);
            return;
        }
    }
}
int main() {
    int u,v,d;
    cin>>N>>t1>>t2;
    for(int i=1;i<N;i++){
        cin>>u>>v>>d;
        g[u].push_back({v,d});
        g[v].push_back({u,d});
    }
    dfs(t1,t2);
    cout<<ans-tmp;
}