RouteOrder | Topcoder Archive

Problem Statement

Time limit: 4 seconds.

Given is a directed graph on N vertices. The vertices are numbered from 0 to N-1.

Edges of the graph have positive integer lengths. For each valid i, there is an edge from X[i] to Y[i] with length L[i].

The graph is simple, i.e., the ordered pairs (X[i], Y[i]) are mutually distinct.

In such a graph, a route is a sequence of integers that describes a simple path from vertex 0 to vertex N-1. This sequence must contain the numbers of vertices in the order in which the path visits them, starting with 0 and ending with N-1. As the path must be simple, the integers in the sequence must be distinct.

We can define a total order on routes as follows: if the routes represent paths of a different length, shorter route is smaller. (Here, the length of a path is the sum of lengths of edges it contains.) If the routes represent paths of the same length, we compare them as integer sequences lexicographically.

Given the graph and the int K, determine and return the route with 0-based index K in the order defined above. Return an empty int[] if no such route exists.

Definition

Class:: RouteOrder
Method:: findPath
Parameters:: int, int[], int[], int[], int
Returns:: int[]
Method signature:: int[] findPath(int N, int[] X, int[] Y, int[] L, int K)
(be sure your method is public)

Constraints

N will be between 2 and 40, inclusive.
X will have between 0 and 500 elements, inclusive.
Y and L will have the same number of elements as X.
Each element of X and Y will be between 0 and N-1, inclusive.
For each i, X[i] will not be equal to Y[i].
The ordered pairs (X[i], Y[i]) will all be distinct.
Each element of L will be between 1 and 9,999, inclusive.
K will be between 0 and 100, inclusive.

Examples

```
3
```
```
{0, 1, 1}
```
```
{1, 2, 0}
```
```
{42, 47, 53}
```
```
0
```
```
Returns: {0, 1, 2 }
```
There is only one simple path from 0 to 2: the path 0->1->2 with length 89. As K = 0, we return the route that describes this path.
```
3
```
```
{0, 1, 1}
```
```
{1, 2, 0}
```
```
{42, 47, 53}
```
```
1
```
```
Returns: { }
```
This is the same graph as in Example 0. There is no route that would correspond to K = 1: even though we have an edge from 1 back to 0, vertices cannot repeat on a simple path.
```
6
```
```
{0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 1, 2, 3, 4}
```
```
{1, 2, 3, 4, 2, 3, 4, 1, 3, 4, 1, 2, 4, 1, 2, 3, 5, 5, 5, 5}
```
```
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
```
```
38
```
```
Returns: {0, 4, 3, 1, 5 }
```
There are: 4 routes of the form {0, x, 5} that represent paths of length 2. 12 routes of the form {0, x, y, 5} that represent paths of length 3. 24 routes of the form {0, x, y, z, 5} that represent paths of length 4. 24 routes of the form {0, x, y, z, w, 5} that represent paths of length 5. The requested route is the penultimate route from the third group.

{0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 1, 2, 3, 4}

{1, 2, 3, 4, 2, 3, 4, 1, 3, 4, 1, 2, 4, 1, 2, 3, 5, 5, 5, 5}

{1, 2, 3, 3, 2, 2, 1, 2, 3, 4, 1, 2, 2, 3, 4, 4, 2, 1, 3, 3}

Returns: {0, 1, 2, 3, 4, 5 }

Now the layout looks the same but the edges have different lengths. This changes the ordering of the routes.

```
40
```
```
{}
```
```
{}
```
```
{}
```
```
0
```
```
Returns: { }
```

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.