You are in a directed weighted graph with $N$ $(63 \le N \le 10^6)$ vertices and $M$ $(1 \le N \le 10^6)$ edges and you want to get from $63^{rd}$ to $4^{th}$ vertex. Going through $i^{th}$ edge takes you $t_i$ hours $(1 \le t_i \le 24)$. A big monster wants to kill you. He appears in the $i^{th}$ edge $f_i$ times per 24 hours randomly. What is the lowest expected value of you meeting with monster?
Input: In the first line we've got $N$ and $M$. In the $M$ following lines there are descriptions of the edges. In each line there is 4 numbers - $a_i, b_i, t_i, f_i$. It means that $i^{th}$ edge is directed from $a_i$ to $b_i$.
Output: You should give one number. The lowest possible expected value of you meeting with monster.
Example:
Input:
64 3
63 4 24 24
63 2 5 1
2 4 5 1
Output:
0.416667
I would think that you could use some adaptation of Dijkstra's algorithm with a min-priority queue where the weight of each edge is the probability of meeting the monster on that edge.