LongLongTripDiv1
SRM 615 · 2013-12-22 · by snuke
SRM 615 · 2013-12-22 · by snuke · Graph Theory, Math
Problem Statement
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 theint 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".
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
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.
Submissions are judged against all 76 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class LongLongTripDiv1 with a public method string isAble(int N, vector<int> A, vector<int> B, vector<int> D, long long T) · 76 test cases · 2 s / 256 MB per case