이번 문제는 다익스트라 알고리즘을 통해 해결하였다. BFS를 통해 두 로봇의 좌표를 관리하며 모든 이동하는 경우를 탐색하는 방법으로 접근하려다가 다익스트라 알고리즘으로 각 로봇의 위치에서 전체 위치로의 거리를 모두 구해놓고, 이를 비교하는 것이 더 깔끔할 것 같다는 생각을 하게 되었다. 이 방식으로 로봇의 위치에서의 모든 거리를 구하고, 두 리스트를 비교하며 값을 구하여 해결하였다.

Code

import heapq
n, r1, r2 = map(int, input().split())
path = [[] for _ in range(n+1)]
for _ in range(n-1):
    a, b, c = map(int, input().split())
    path[a].append((b, c))
    path[b].append((a, c))
if n == 1 or r1 == r2:
    print(0)
    quit()
def get_dist(r):
    q = []
    heapq.heappush(q, (0, r))
    dists = [1e9 for _ in range(n+1)]
    dists[r] = 0
    while q:
        dist, cur = heapq.heappop(q)
        if dist > dists[cur]:
            continue
        for nxt, dst in path[cur]:
            nxt_dist = dist+dst
            if dists[nxt] > nxt_dist:
                dists[nxt] = nxt_dist
                heapq.heappush(q, (nxt_dist, nxt))
    return dists
dists1 = get_dist(r1)
dists2 = get_dist(r2)
answer = 1e9
for cur in range(1, n+1):
    for nxt, dist in path[cur]:
        answer = min(answer, dists1[cur]+dists2[nxt], dists1[nxt]+dists2[cur])
print(answer)