Java
Time Limit 1000MS
Memory Limit 256MB
12.15
In the parallel universe, you are a very famous artist. You have drawn a priceless painting. One day the mayor of the city comes to you. He wants you to give an exhibition in the city museum. But the problem is the painting is too big (10m * 6.18m). You are unable to move it by yourself. So you call your friend to help you. The painting will be split into two parts. Each of you will carry half of it. However, in terms of the security of the painting, you dont want to meet your friend in any location during the transport because once you meet him two parts are combined into one whole artifact which is easily stolen by the criminals. So your friend will go first. You stay at home to wait the phone call from him. He will call you Once he arrives the museum. After receiving the call, you set out to move the left part. Both you and your friend want to go to the museum as soon as possible. So each time the shortest path to the museum is preferred. But you shouldnt pass any location he passed before except your home and museum because some criminals around those locations will notice what you are doing. Before the adventure, you want to know the time gap between he leave your home and two parts meet in the museum. Assuming the phone call consumes 0 minutes.(Hint: Memory Limit Exceeded means you allocate too much memory)
Input
First line: n (50% cases:1<=n<=1000, 100% cases:1<=n<=10000) . Second line: m (1<= m<=20000). Locations are numbered from 1 to n. Your home at 1. The next m lines will each contain 3 integers, i, j and c, meaning that there is a street between location i and j with c minutes to run through the street. (0<=c<=1000).The position of your home is at 1 and the position of the museum is at n.OutputOutput a single integer on a line by itself – the number of minutes you and your partner need between the time he leaves and the time both of you meet at the museum. If there is no solution, print “OMG!”.331 3 102 1 203 2 509121 2 101 3 101 4 102 5 103 5 104 5 105 7 106 7 107 8 106 9 107 9 108 9 10
Reviews
There are no reviews yet.