[백준] 15971 - 두 로봇

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

15971번: 두 로봇

 

두 정점 간의 최단 거리에서, 경로에 포함되어있는 최대 가중치를 빼는 문제이다.

dfs를 이용해 s부터 임의의 정점까지의 거리를 구하는 dist배열과 경로 상 최대 가중치를 저장하는 maxW 배열을 채워넣는다.

 

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

int n, s, d;
vector<vector<pair<int, int>>> v;
int dist[100001], maxW[100001];

void go(int node, int pre, int w, int cost) {
	dist[node] = cost;
    maxW[node] = w;
    
    for(auto& i : v[node]) {
    	if(i.first != pre) {
        	go(i.first, node, max(w, i.second), cost + i.second);
        }
    }
}

int main() {
	
    cin >> n >> s >> d;
    v.resize(n + 1);
    
    for(int i = 0; i < n - 1; i++) {
    	
        int a, b, c;
        cin >> a >> b >> c;
        
        v[a].push_back({ b,c });
        v[b].push_back({ a,c });
    }
    
    if(s == d) cout << 0;
    else {
        go(s, 0, 0, 0);
        cout << dist[d] - maxW[d];
    }
    
}