SHEEPNAM - Nam The Sheep Watcher
It's Friday afternoon. Nam and Ryan decided to go on a bike ride on the Darebin Creek Trail. The trail can be described as a tree with n nodes A1, A2 … An representing the crossroads. There are n-1 roads connecting the nodes, and the time it takes to ride from node Ai to node Bi (or from Bi to Ai, you can go either way) is Ti (1 ≤ Ai, Bi ≤ n, 1 ≤ i ≤ n-1, 1 ≤ Ti ≤ 10^9).
Nam and Ryan start the trip from Uni, which is at node X. Because Nam has never seen a sheep, Ryan decided to take Nam to a field nearby at node Y where, for some reason, there is a lot of sheep.
Riding bikes and seeing sheep are fun and all, but Nam also needs to go home by 7 pm to play his favorite game, Doki Doki Literature Club. Therefore, Nam wants to know how long it will take to get to the sheep.
Requirement
Calculate the time it takes for Nam and Ryan to travel from Uni (node X) to the sheep field (node Y).
Input
- The first line contain three integer n, X, Y (n <= 10^5, 1 <= X, Y <= n)
- The following n-1 lines, each contains 3 integers Ai, Bi, and Ti (1 <= Ai, Bi <= n, 1 <= i <= m, 1 <= Ti <= 10^9).
Output
A single integer which is the answer.
Example
Input: 6 2 6 1 2 2 2 3 1 2 4 5 4 6 2 4 5 4 Output: 7
Added by: | LTU ComSoc |
Date: | 2022-04-14 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |