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.
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
Nieuwkerk 0 -5 0
Oudekerk 10 0 0
Pierteck -100 -100 0
0 Output: Case #1:
Nieuwkerk-Pierteck NOT REACHABLE
Oudekerk-Pierteck NOT REACHABLE
Thanks to SourSpinach for crucial info.
Please, someone, explain how Pierteck-Oudekerk is -105 ?
thanks @Jacob Plachta. i got acc
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.
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.
1. Output NEGATIVE CYCLE for all of a test case's queries if there's a negative cycle anywhere in the graph.
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.
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
I always enjoy problems involving negative cycles :)
Input limits are not given and they should be.