ColorfulPath | Topcoder Archive

Problem Statement

This is a shortest path problem. You will be given a specific directed graph. Your task is to find the shortest path from one vertex to another, while satisfying some constraints.

The graph has n+1 vertices, numbered 0 through n. The path we seek should start in vertex 0 and end in vertex n.

You are given three equally-long int[]s: a, b, and cost. For each i, our graph contains a directed edge from the vertex a[i] to the vertex b[i], and the length of this edge is cost[i].

The graph has a very special shape. In particular, the edges satisfy the following constraints:

For each i we have a[i] < b[i]. (Note that this makes our graph acyclic.)
There are no i,j such that a[i] < a[j] < b[i] < b[j].

Each of the vertices 1 through n-1 has a color. You are given these colors in the int[] color. Different numbers represent different colors. Note that color[i] is the color of vertex (i+1).

Also note that n is not given explicitly. Instead, you can determine n as (1 + the number of elements in color). That is, the total number of vertices is (2 + the number of elements in color).

For each color, you must either visit all vertices with that color, or none of them. In other words: For any two vertices x,y in {1 ... n-1}, if they have the same color, then you must either visit both of them or visit neither.

If there is no valid path from 0 to n, return -1. Otherwise, return the smallest possible total length of such a path.

Definition

Class:: ColorfulPath
Method:: shortestPath
Parameters:: int[], int[], int[], int[]
Returns:: int
Method signature:: int shortestPath(int[] a, int[] b, int[] cost, int[] color)
(be sure your method is public)

Constraints

n will be between 2 and 1,000, inclusive.
a will contain between 1 and 1,000 elements, inclusive.
a, b and cost will contain the same number of elements.
Each element in a, b will be between 0 and n, inclusive.
Each element in cost will be between 1 and 1,000,000, inclusive.
For each i, a[i] < b[i].
There are no i and j such that: a[i] < a[j] < b[i] < b[j].
color will contain exactly n-1 elements.
Each element in color will be between 1 and 1,000, inclusive.

Examples

```
{0,0,1,2}
```
```
{1,2,2,3}
```
```
{10,10,10,10}
```
```
{1,2}
```
```
Returns: 20
```
Our graph has vertices {0,1,2,3}. There are four directed edges: 0 -> 1, 0 -> 2, 1 -> 2, and 2 -> 3. Each edge has length 10. The vertices 1 and 2 have different colors, so there are no restrictions on our path. The shortest path in this setting is 0 -> 2 -> 3. Its length is 10 + 10 = 20.
```
{0,0,1,2}
```
```
{1,2,2,3}
```
```
{10,10,10,10}
```
```
{1,1}
```
```
Returns: 30
```
We have the same graph but different colors, this time 0 -> 2 -> 3 is not valid since we will visit node 2 but not node 1 while they have the same color.
```
{0,0,2}
```
```
{1,2,3}
```
```
{10,10,10}
```
```
{1,1}
```
```
Returns: -1
```
The only path is 0 -> 2 -> 3 but it is invalid.

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

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

{1,1,1,100,1,10,10}

{1,2,3,1}

Returns: 20

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

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

{1,1,1,100,1,10,10}

{1000,900,800,700}

Returns: 13

{0,8,1,0,7,3,4,9,7,1,2,7,7,0,7,6,0,0,3,5,7,8,2}

{7,9,3,7,9,6,6,10,9,2,3,10,8,1,9,7,6,3,6,6,9,9,3}

{1663,101,1455,4839,1357,1045,1734,851,1384,941,351,1551,611,953,658,746,5850,123,434,317,732,451,555}

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

Returns: 3214

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.