Traffic Lights

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 16M

Problem type

Jim-Bob lives in a strange city where the streets don't necessarily run NS or EW. Instead the NN (1 \le N \le 100\,000)(1 \le N \le 100\,000) streets run seemingly at random, sometimes crossing over each other by bridges, and intersecting with one another at exactly KK (1 \le K \le 1\,000)(1 \le K \le 1\,000) intersections. Each intersection consists of some streets coming together, as well as a traffic light.

Street ii starts at intersection s_is_i (1 \le s_i \le K)(1 \le s_i \le K), and ends at a different intersection e_ie_i (1 \le e_i \le K)(1 \le e_i \le K), going through no other intersections in between. It takes t_it_i (1 \le t_i \le 1\,000)(1 \le t_i \le 1\,000) minutes to travel down street ii (this number is derived from the length, the average pothole size, and the amount of roadkill). Each road can be travelled in either direction in the same amount of time.

The traffic lights in this city are also strange. First of all, each one only alternates between green and red. Each light also cycles through these colours at a different rate – the traffic light located at intersection ii stays green for g_ig_i (1 \le g_i \le 1\,000)(1 \le g_i \le 1\,000) minutes, then stays red for r_ir_i (1 \le r_i \le 1\,000)(1 \le r_i \le 1\,000) minutes, then goes back to green, and so on.

Jim-Bob always obeys the law, and will never run a red light. If he arrives at an intersection while the light is green, he can pass right through it. Otherwise, he must wait there until the light turns green. If he gets to an intersection just as the traffic light is turning red, he must wait. It takes no time to drive through an intersection, so the light will never turn red on him as he drives through.

Jim-Bob starts at his house, also known as intersection 11. As soon as he leaves his house, all the traffic lights turn green, starting their green-red-green cycle. He wishes to drive to Billy-Bob's house (which is right at intersection KK) as fast as possible. Neither the starting nor the finishing intersection have traffic lights, so their gg and rr will be given as 00. Find the minimum number of minutes Jim-Bob can take to drive from his house to Billy-Bob's.

Input Specification

22 integers – NN and KK.
The next NN lines contain 33 integers each – s_is_i, e_ie_i, and t_it_i.
The next KK lines contain 22 integers each – g_ig_i, and r_ir_i.

Output Specification

A single integer – the minimum number of minutes it takes to drive from Jim-Bob's house to Billy-Bob's. It will always be possible to do this.

Sample Input

7 6
1 2 4
1 3 1
3 5 2
2 4 2
2 5 6
5 4 2
5 6 10
0 0
5 5
1 20
2 5
10 2
0 0

Sample Output



The city looks something like this (Jim-Bob's best route is shown in red):

Jim-Bob can drive to intersection 22 (44 min), drive on to intersection 44 (22 min), wait for the green light (11 min), drive down to intersection 55 (22 min), and finally drive to Billy-Bob's house (1010 min). This is a total of 1919 minutes.

Note: The traffic light at intersection 33 only stays green for 11 minute, which means that Jim-Bob would just miss it if he drove directly there. On the other hand, he makes the green lights as intersections 22 and 55 just in time, as they turn red 11 minute after he passes.


There are no comments at the moment.