RunningTrail | Topcoder Archive

Problem Statement

I like to run. When I move to a new area, I want to explore the surroundings and locate a good running trail. There are many paths and junctions I can choose to be part of my running trail, but I want the total length of the trail to be as close to a specific length as possible (but always greater than zero). Given a set of paths as a String[], determine a trail consisting of at least one path whose length is as close to the desired length as possible. While I don't mind running the same path several times (see example 0), I don't want to run to a junction at the end of a path, and then turn around and run back to the previous junction along the same path (see example 1).

Each path will be described by a String in the format (quotes for clarity only) "<junctionA> <junctionB> <length>", where junctionA, junctionB and length are all positive integers. Several paths might go between the same two junctions, and I can run along a path in both directions. The trail should always start and end at junction 1. Create a class RunningTrail containing the method bestTrail which takes a String[] paths and an int desiredLength, and returns an int containing the length of the trail closest to the desired length. In case there are several trails equally close to the desired length, return the length of the shortest of them.

Definition

Class:: RunningTrail
Method:: bestLength
Parameters:: String[], int
Returns:: int
Method signature:: int bestLength(String[] paths, int desiredLength)
(be sure your method is public)

Constraints

paths will contain between 2 and 50 elements, inclusive.
desiredLength will be between 1 and 100000, inclusive.
Each element in paths will be in the format above, with no leading zeros or extra spaces.
In each element of paths, <junctionA> and <junctionB> will be integers between 1 and 50, inclusive.
In each element of paths, <junctionA> and <junctionB> will be distinct.
In each element of paths, <length> will be an integer between 1 and 5000, inclusive.
All paths in paths will be reachable from junction 1.
At least one trail of positive length will exist that starts and ends at junction 1.

Examples

```
{"1 2 1200","2 3 700","1 5 1450","2 6 650","5 6 650","6 4 1500","3 4 900"}
```
```
10000
```
```
Returns: 9900
```
It's not possible to find a trail of length 10000, but the closest is 9900. Such a trail can be obtained by selecting the paths going through the junctions 1-2-3-4-6-2-3-4-6-2-1.
```
{"1 2 1000","2 3 500","3 4 500","2 4 500"}
```
```
2500
```
```
Returns: 3500
```
The trail from node 1 to 2 and back again to 1 would be closer to the desired length, but that's not an allowed trail.
```
{"1 2 1000","2 3 500","3 4 500","2 4 500","1 2 1000"}
```
```
2500
```
```
Returns: 2000
```
Same as the previous example, but now there are two paths from junction 1 to 2, so it's possible to run from junction 1 to 2 and then back again.

{"1 2 47","2 3 16","3 4 42","4 1 12","1 5 40","5 6 5",
 "6 7 50","7 8 9","8 1 44","3 9 8","9 10 29","10 3 44",
 "5 11 19","11 12 33","12 13 9","13 5 49"}

Returns: 397

```
{"1 2 2", "2 1 2"}
```
```
1
```
```
Returns: 4
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.