22194번 - Museum 서브태스크다국어

문제

A tourist just walked into a museum that houses a treasured collection of clean drinking water from different parts of the world. Fortunately, it is only a temporary exhibition to raise awareness but might become a permanent thing in the future.

The museum consists of n rooms (numbered from 1 to n) that are connected with each other by doors and passages. Each passage connects two rooms directly, without passing through other rooms. The layout of the museum is such that between every pair of rooms, there is exactly one simple path (possibly passing through one or more intermediary rooms). The tourist is currently located in room x. He has a map of the museum and thus knows for every passage i that it connects rooms a_i and b_i, and that it takes c_i time to walk the length of that passage.

He would like to visit k different rooms (including the starting room x). He will spend an insignificant amount of time in every room. It doesn’t matter in which room he finishes his visit. What is the shortest possible time in which he can achieve this?

입력

First line contains integers n, k and x. The following n−1 lines describe passages between rooms with integers a_i, b_i and c_i, indicating that there is a passage between rooms a_i and b_i that takes c_i time to move through.

출력

Output the minimum time required to visit k rooms.

제한

• 1 ≤ n ≤ 10 000
• 1 ≤ k, x ≤ n
• 1 ≤ a_i, b_i ≤ n
• 0 ≤ c_i ≤ 10 000

서브태스크 1 (20점)

• n ≤ 20

서브태스크 2 (25점)

• k ≤ 100
• Every room has at most 3 adjacent rooms

서브태스크 3 (35점)

• k ≤ 100

서브태스크 4 (20점)

• No additional constraints

힌트