Problem B: Stack Machine
A mathematician observes one person get on a bus. Then two people get
off the bus. The mathematician says: "If one more person gets on the
bus, the bus will be empty."
A stack machine is a special kind of bus. It only has doors
at the front, and it is so narrow that the people on the bus
cannot move past each other. Of the people on the bus, the
person who got on the bus last must be the first to get off.
The bus travels in a city in which roads connect intersections,
and all the roads are unidirectional. Along each road, a
person either gets on or off the bus.
The mathematician does not know the identity of the bus passengers,
but can estimate their height. Note that there may be multiple
people with the same height.
Your task is to plan the route of the bus. The bus must be empty
at the beginning and end
of the route. Along the route, it must pick up and drop off the
people corresponding to the roads it travels on. The height of the
person that gets on or off the bus is fixed for each road.
Input Specification
The first line of input contains a single integer, the number of test
cases to follow. Each test case begins with a line containing three
integers N, M, Q, the number of intersections and roads
in the city and the number of queries, respectively. The number of intersections is between 1
and 100, inclusive. The number of roads and the number of queries
are each between 1 and 100000, inclusive.
Intersections in the city are numbered from 1 to N.
The first line of each test case is followed by M lines describing
the roads. Each of these lines contains three integers X, Y, and Z.
These integers indicate that a road exists from intersection X to
intersection Y, and that when the bus travels on this road, a person
who is Z centimetres tall gets on the bus, if Z is positive, or a person who
is
-Z centimetres tall gets off the bus, if Z is negative. For example, Z=170 indicates that
a 170 cm tall person gets on the bus, and Z=-170 indicates that a 170 cm tall person gets off the bus.
Each person is at least 40 cm and at most 220 cm tall.
The lines describing the roads are followed by Q more lines, each
describing a query. A line describing a query contains two integers,
the beginning and ending intersections of the bus route.
Sample Input
1
2 2 4
1 2 100
2 1 -100
1 1
2 2
1 2
2 1
Output Specification
For each query, output a line containing a single integer giving the
length of the shortest non-empty path that the bus can take from the
beginning to the end of the route. The input data will be such that this
length is no more than 10^9. If there is no such path, output
a line containing the word impossible.
Output for Sample Input
2
impossible
impossible
impossible
Ondřej Lhoták
This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.