Connection Status:
Competition Arena > RouteOrder

RouteOrder

SRM 841 · 2022-11-07 · by misof

SRM 841 · 2022-11-07 · by misof · Graph Theory, Greedy
Class Name: RouteOrder
Return Type: int[]
Method Name: findPath
Arg Types: (int, vector<int>, vector<int>, vector<int>, int)
Problem Statement

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.

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
0)
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.

1)
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.

2)
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.

3)
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}
64
Returns: { }
4)
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, 2, 3, 3, 2, 2, 1, 2, 3, 4, 1, 2, 2, 3, 4, 4, 2, 1, 3, 3}
38
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.

Submissions are judged against all 118 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RouteOrder with a public method vector<int> findPath(int N, vector<int> X, vector<int> Y, vector<int> L, int K) · 118 test cases · 2 s / 256 MB per case

Submitting as anonymous