[백준] 15971 두 로봇

15971번: 두 로봇

 

www.acmicpc.net

풀이

두 로봇을 양 시작점과 끝점이라고 생각하면, 시작점부터 끝점까지의 길이의 합에서 가장 긴 길이를 빼면 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool finish = false;
int n, r1, r2;
vector<pair<int, int>> adj[100001];
bool visited[100001];

void dfs(int idx, int sum, int max_value){
    // 답을 찾았으면 탐색을 종료
    if (finish) return;
    // 경로를 다 찾은 경우
    if (idx == r2) {
        finish = true;
        cout << sum - max_value << '\n';
        return;
    }

    visited[idx] = true;

    for (auto i : adj[idx]) {
        int next = i.first;
        int value = i.second;
        if (!visited[next]) 
            dfs(next, sum + value, max(max_value, value));
    }
}

int main() {
    cin >> n >> r1 >> r2;
    for (int i = 0; i < n - 1; i++) {
        int tmp1, tmp2, v;
        cin >> tmp1 >> tmp2 >> v;
        adj[tmp1].push_back({ tmp2, v });
        adj[tmp2].push_back({ tmp1, v });
    }

    dfs(r1, 0, 0);
    return 0;
}