DrivingPlans | Topcoder Archive

Problem Statement

You live in a city with N intersections, numbered 1 through N. There are some roads in the city. Each road is bidirectional and connects two intersections. There are no loops and each pair of intersections is connected by at most one road. The road network is connected - that is, one can travel between any two intersections.

A special feature of this city is that some of the roads have no speed limits, and everyone drives along those roads at an insane speed. For the purpose of this problem, we will simply assume that these roads can be traversed instantly, in zero time.

You are given the int N and three int[]s A, B, and C, each with the same number of elements. The int[]s A, B, and C describe the road network: For each valid i, there is a bidirectional road that connects the intersections A[i] and B[i], and it takes C[i] seconds to traverse that road in either direction.

You are currently at the intersection 1 and you want to travel to the intersection N as quickly as possible. Count all ways of doing so, and return that count modulo 1,000,000,009. If there are infinitely many ways, return -1 instead. (Two ways are considered different if the sequences of visited intersections differ. Note that it is allowed to enter any intersection, including intersections 1 and N, multiple times.)

Definition

Class:: DrivingPlans
Method:: count
Parameters:: int, int[], int[], int[]
Returns:: int
Method signature:: int count(int N, int[] A, int[] B, int[] C)
(be sure your method is public)

Constraints

N will be between 2 and 2,000, inclusive.
A, B and C will contain between 1 and 2,000 elements, inclusive.
A, B and C will contain the same number of elements.
Each element of A and B will be between 1 and N, inclusive.
Each element of C will be between 0 and 100,000, inclusive.
For each valid i, A[i] will be different from B[i].
No two roads will connect the same pair of intersections.
The road network will be connected.

Examples

```
4
```
```
{1,1,2,3}
```
```
{2,3,4,4}
```
```
{1,1,1,1}
```
```
Returns: 2
```
There are exactly two shortest ways of travel: 1-2-4 and 1-3-4.
```
4
```
```
{1,1,2,3}
```
```
{2,3,4,4}
```
```
{1,1,1,0}
```
```
Returns: -1
```
Remember that each road can be used in both directions. In this case, there are infinitely many ways how to reach the intersection 4 in shortest time. For example, you can go 1-3-4, or 1-3-4-3-4, or 1-3-4-3-4-3-4, etc.

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

{2,3,4,4,5,6,7,7}

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

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.