LongLongTripDiv1 | Topcoder Archive

Problem Statement

There is a country with N cities. The cities are numbered 0 through N-1. There are some bidirectional roads in the country. Each road connects a pair of cities. More precisely, for each i, road i connects the cities A[i] and B[i].

Limit is a deer that likes to travel along the roads. Traveling along road i (in either direction) takes him exactly D[i] minutes. Limit does not like cities, so he never waits in a city.

Limit is currently in the city 0, starting his travels. In exactly T minutes, he wants to be in the city N-1.

You are given the int N; the int[]s A, B, and D; and the long T. Return "Possible" (quotes for clarity) if Deer Limit can reach city N-1 in exactly T minutes. Otherwise, return "Impossible".

Definition

Class:: LongLongTripDiv1
Method:: isAble
Parameters:: int, int[], int[], int[], long
Returns:: String
Method signature:: String isAble(int N, int[] A, int[] B, int[] D, long T)
(be sure your method is public)

Constraints

N will be between 2 and 50, inclusive.
A will contain between 1 and 50 elements, inclusive.
A, B and D will each contain the same number of elements.
Each element in A and B will be between 0 and N-1, inclusive.
Each element in D will be between 1 and 10,000, inclusive.
For each valid i, A[i] and B[i] will be different.
No two roads will connect the same pair of cities.
T will be between 1 and 10^18, inclusive.

Examples

{0,0,1}

{2,1,2}

{7,6,5}

Returns: "Possible"

city 0 -> city 1 -> city 2 is a valid way.

```
3
```
```
{0,0,1}
```
```
{2,1,2}
```
```
{7,6,5}
```
```
25
```
```
Returns: "Possible"
```
city 0 -> city 2 -> city 1 -> city 0 -> city 2 is a valid way.
```
2
```
```
{0}
```
```
{1}
```
```
{1}
```
```
9
```
```
Returns: "Possible"
```
Here, Limit just travels back and forth between cities 0 and 1 along the only road in the country.

{1}

{0}

{1}

1000000000000000000

Returns: "Impossible"

```
4
```
```
{0,0,1}
```
```
{2,1,2}
```
```
{10,10,10}
```
```
1000
```
```
Returns: "Impossible"
```
In this test case, there is absolutely no way how to reach city N-1 from city 0.

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

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

{6580,8822,1968,673,1394,9337,5486,1746,5229,4092,195}

937186357646035002

Returns: "Impossible"

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.