UCV2013B - Alice in Amsterdam, I mean Wonderland

no tags 

This is a fact that not many people know, but Alice lived in Amsterdam. Yes, there you go. And as many kids of the time, she used to go for some medicinal mushrooms to the drug store (the pharmacies, the coffee shops didn't exist yet). Usually, between the regular mushrooms, a magical one could be found, producing as expected, deep and vivid hallucinations. During one of those hallucinations, Alice was transported to a "wonderland", where many weird things happened. One thing was particularly dazzling for her: even though everything looked pretty familiar, the distance between monuments of the city was sometimes negative!!! Although, zero distance between two different monuments means a direct path doesn't exist. A loop from a given monument right back to it can be of length zero (with means that it can be reached instantly like in real life) or negative, like for regular paths. Alice also thought that she saw some positive distances for loops, but we should treat those cases as zero distance.

Now, as a very smart girl as she is, she figured out a way to find the shortest path between any two monuments. Unfortunately, as expected, Alice forgot it when she got sober again. She was only able to remember that, in some cases, she could get stuck in a cycle path with negative distance. In such cases, there will always be a cheaper path to get to the same monument. This was one of the few things that had perfect sense for her: Your shortest path will be shorter if you take that cycle again and again, to infinity. Alice, has been trying to figure optimal distances all over again, but she can't. She doesn't want to trip again, she has been clean for longer than a year (good for her!!). Would you be so kind to help her?

Given a list of monuments in a city, and their relative distances, find the shortest paths between some pairs of monuments.


Each case, starts with one line containing N, the number of monuments in the test case (1 <= N <= 100). Next N lines will each contain one string K and N integers Kj, separated by single spaces. K is a name of a monument and will consist of at most 20 alphanumeric characters. Each integer Kj (0 <= j < N) in line i describes the distance from monument i to j (-2^30 <= Kj <= 2^30). Next line will contain a single integer Q (1 <= Q <= N^2). It will be followed by Q lines, each with a pair of integers (U, V), indicating the start and destination monument for the path that is queried (0 <= U, U < N).
End of the input is indicated by a test case with N = 0 and should not be processed.


For each test case, print a line "Case #tc:" (without quotes), where tc is the case number, starting from 1. Next Q lines should describe query results. If the optimal distance can be infinitely small, print only "NEGATIVE CYCLE". In other cases, start the line with "start_name-destination_name" followed by the actual result. If the destination can't be reached, print "NOT REACHABLE", otherwise print the integer distance.


Nieuwkerk -1 1
Oudekerk 1 0
0 0
0 1
1 1
1 0
Nieuwkerk 0 -5 0
Oudekerk 10 0 0
Pierteck -100 -100 0
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
0 Output: Case #1:
Case #2:
Nieuwkerk-Nieuwkerk 0
Nieuwkerk-Oudekerk -5
Nieuwkerk-Pierteck NOT REACHABLE
Oudekerk-Nieuwkerk 10
Oudekerk-Oudekerk 0
Oudekerk-Pierteck NOT REACHABLE
Pierteck-Nieuwkerk -100
Pierteck-Oudekerk -105
Pierteck-Pierteck 0

hide comments
jdmoyle: 2021-09-04 23:17:32

What if ,say any query from u to v, if v is not reachable from u but while traversing from u a negative cycle is found ;
what will be the answer in this case ? NOT REACHABLE or NEGATIVE CYCLE

rushi2001: 2021-06-16 17:37:14

@Jacob Plachta
See his comments to get AC , but again i don't think it is the valid solution as if we
have more the one connected components and one component contains negative cycle so this cycle cannot reduce the distance between pairs of other components.
So i think testcases are so weak or might be the solution .

I think solution should be if you are asked to check the path for u to v check for both cities if any one contain negative cycle then this path contain negative cycle otherwise distance exists or it is not reachable .

Last edit: 2021-06-17 17:34:58
nadstratosfer: 2018-06-20 08:26:07

Thanks to SourSpinach for crucial info.

Nidhi: Pierteck-Nieuwkerk-Oudekerk = -100 + (-5) = -105.

For better understanding of the problem, https://www.youtube.com/watch?v=PKYUz7kx3jA =)

Last edit: 2018-06-20 08:49:08
nidhi_061: 2018-06-19 22:17:57

Please, someone, explain how Pierteck-Oudekerk is -105 ?

Jose Sanchez: 2013-07-26 20:22:08

thanks @Jacob Plachta. i got acc

Rocker3011: 2013-07-25 22:30:16

What the comment below Miguel says is wrong, as the graph can be disconected, the negative cycle he states is wrong, the whole graph doesn't get negative cycle if you find one.

Costed me about all my W.A, needed help to find such a silly mistake. Also i did not take in account many things that are said in the comments and managed accepted. So, do not read the comments... just code :)

Last edit: 2013-07-25 22:33:25
Miguel Oliveira: 2013-07-25 20:49:58

I only output NEGATIVE CYCLE if the negative cycle is reachable by U. Since Jacob has his solution accepted, it seems there is no such case in the test data.

Jacob Plachta: 2013-07-25 02:30:42

1. Output NEGATIVE CYCLE for all of a test case's queries if there's a negative cycle anywhere in the graph.
2. If the distance from a node to itself is given as being positive, treat is as 0 instead.

Shaka Shadows: 2013-07-24 19:54:51

I got AC in this problem, but making an assumption not said in the statement. I've set distance from i to i = 0, despite the corresponding input value. I think that should be somehow in the description. I got a lot of WA due to that.

Shaka Shadows: 2013-07-24 14:42:47

I think that problem statement is not totally clear about negative cycles existence. When exactly should I report their existence in path from u to v?

Last edit: 2013-07-24 15:24:58

Added by:Hector Navarro
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Local UCV 2013. Ignacio Calderón