UCV2013B  Alice in Amsterdam, I mean Wonderland
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.
Input
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.
Output
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_namedestination_name" followed by the actual result. If the destination can't be reached, print "NOT REACHABLE", otherwise print the integer distance.
Example
Input: 2
Nieuwkerk 1 1
Oudekerk 1 0
4
0 0
0 1
1 1
1 0
3
Nieuwkerk 0 5 0
Oudekerk 10 0 0
Pierteck 100 100 0
9
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
0 Output: Case #1:
NEGATIVE CYCLE
NEGATIVE CYCLE
NEGATIVE CYCLE
NEGATIVE CYCLE
Case #2:
NieuwkerkNieuwkerk 0
NieuwkerkOudekerk 5
NieuwkerkPierteck NOT REACHABLE
OudekerkNieuwkerk 10
OudekerkOudekerk 0
OudekerkPierteck NOT REACHABLE
PierteckNieuwkerk 100
PierteckOudekerk 105
PierteckPierteck 0
hide comments
jdmoyle:
20210904 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 ;


rushi2001:
20210616 17:37:14
@Jacob Plachta


nadstratosfer:
20180620 08:26:07
Thanks to SourSpinach for crucial info.


nidhi_061:
20180619 22:17:57
Please, someone, explain how PierteckOudekerk is 105 ?


Jose Sanchez:
20130726 20:22:08
thanks @Jacob Plachta. i got acc 

Rocker3011:
20130725 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.


Miguel Oliveira:
20130725 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:
20130725 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.


Shaka Shadows:
20130724 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:
20130724 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: 20130724 15:24:58 
Added by:  Hector Navarro 
Date:  20130722 
Time limit:  1s2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Local UCV 2013. Ignacio CalderÃ³n 