Jakarta Traffic Jam

Interview

Time limit1sMemory limit128 MB

Summary

Find the fastest travel time between two intersections where each street is driven at half speed during its own daily rush hour, and you never stop to wait. Each test case gives up to 20 nodes; report the minimum minutes to two decimals.

Level: Medium7 of 10
Topics: Graph, Shortest path, Simulation, Implementation
Solved: No attempts yet

Problem

Traffic in Jakarta is terrible. During rush hour the streets get congested, and while a street is congested you can only drive at half of your normal speed. So you must plan your trip carefully if you do not want to be late.

For example, suppose a street from P to Q normally takes $20$ minutes to drive, and it is congested from 15:00 until 16:00. Consider a few situations:

If you leave P $15$ minutes before rush hour starts (at 14:45), you cover $15$ minutes' worth of distance at normal speed before the congestion begins. The remaining distance is worth $5$ normal minutes, but at half speed it takes $10$ minutes to cover. So the whole trip from P to Q takes $15 + 10 = 25$ minutes.
If you leave during the last $5$ minutes of rush hour (at 15:55), the distance you cover in those first $5$ congested minutes equals $2.5$ minutes' worth at normal speed. The remaining distance is worth $17.5$ normal minutes, and since rush hour is now over it takes $17.5$ more minutes. So the trip takes $5 + 17.5 = 22.5$ minutes.
Other combinations of the above are possible.

In other words, whenever you are on a street during its rush hour you move at half speed, and otherwise at normal speed. Each street's rush hour is defined within a single day and never rolls over past midnight.

Given a map with at most $N$ intersections and $M$ streets, find the minimum time needed to travel from $s$ to $d$ , in minutes. Assume you drive continuously without stopping to wait.

Input

The input contains several test cases.

Each test case begins with a line containing two integers $N$ ( $1 \le N \le 20$ ) and $M$ , the number of intersections and the number of streets. Intersections are numbered starting from $0$ .

Each of the next $M$ lines describes one street. A line starts with three integers $P$ , $Q$ , and $T$ ( $1 \le T \le 50$ ), meaning there is a street connecting intersection $P$ and intersection $Q$ that takes $T$ minutes to drive at normal speed (streets are two-way). These are followed by the character N or R. N has nothing after it and means the street has no rush hour. R is followed by the start and end time of the rush hour in hh:mm format (from 00:00 to 23:59). No rush hour rolls over past midnight.

The last line of each test case contains the starting point $s$ , the destination $d$ , and the current time $w$ in hh:mm format.

The input is terminated by a line containing two zeros, which must not be processed.

Output

For each test case, output on its own line the minimum time in minutes needed to go from $s$ to $d$ . Always print exactly two digits after the decimal point.

Examples3

Example 1

Input

2 1
0 1 20 R 15:00 16:00
0 1 14:45
3 3
0 1 20 R 15:00 16:00
1 3 10 N
2 1 35 R 16:30 17:00
0 2 15:55
0 0

Expected output

25.00
72.50

Example 2
Input
```
2 1
0 1 20 N
0 1 08:00
0 0
```
Expected output
```
20.00
```

Example 3

Input

2 1
0 1 20 R 15:00 16:00
0 1 15:55
0 0

Expected output

22.50