JOIN
Get Time

   Problem Statement  

 Problem Statement for LongLongTripDiv1

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)
    
3
{0,0,1}
{2,1,2}
{7,6,5}
11
Returns: "Possible"
city 0 -> city 1 -> city 2 is a valid way.
1)
    
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)
    
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.
3)
    
2
{1}
{0}
{1}
1000000000000000000
Returns: "Impossible"
4)
    
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.
5)
    
9
{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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 615 Round 1 - Division I, Level Two