[15971] 두 로봇

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

15971번: 두 로봇

<문제>

하나의 로봇에서 다른 로봇까지의 최단경로를 찾았다고 생각해보자

로봇이 하나의 간선을 사이로 두는것이 종료조건이라면, 해당 간선은 지나갈 필요가 없으니

결국 가장 거리가 먼 간선을 사이에 두는것이 항상 최적이다.

bfs를 이용해 해당 경로를 전부 누적하며, 도착하면 경로에 포함된 간선중 가장 큰것을 빼주면 된다.

 

<소스코드>

#include <bits/stdc++.h>
using namespace std;
typedef struct {
    int node, sum, mx;
} state;
queue<state> q;
vector<pair<int, int>> adj[100001];
int n, s, e;
bool visited[100001];
int main(void) {
    cin >> n >> s >> e;
    int i;
    for (i = 0; i < n - 1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    q.push({s, 0, 0});
    visited[s] = true;
    while (!q.empty()) {
        state cur = q.front();
        q.pop();
        if (cur.node == e) {
            cout << cur.sum - cur.mx;
            return 0;
        }
        for (auto& next : adj[cur.node]) {
            if (visited[next.first] == false) {
                visited[next.first] = true;
                q.push({next.first, cur.sum + next.second,
                        max(cur.mx, next.second)});
            }
        }
    }
    return 0;
}