Let ~f(i,j)~ be the chance of arriving on time if you're at station ~i~ with ~j~ minutes left.

Let ~ex(i,j)~ be the expected value of ~X~ if you're at station ~i~ with ~j~ minutes left.

Let ~g(i,j)=f(i,j) \cdot ex(i,j)~.

Let ~b_{mn}~ be the value of ~b_i~ corresponding to the ~n^{th}~ edge leaving station ~m~. ~x_{mn}~ and ~y_{mn}~ are defined similarly.

Let ~q_i~ be the number of edges leaving station ~i~.

Then:

$$\displaystyle \begin{align*} f(i,j) &= \sum_{k=1}^{q_i} \frac{1}{q_i} \left(\frac{\sum_{z=j-x_{ik}}^{j-y_{ik}} f(b_{ik},z)}{y_{ik}-x_{ik}+1}\right) \\ g(i,j) &= \frac{1}{f(i,j)} \sum_{k=1}^{q_i} \frac{1}{q_i} \left(\frac{\sum_{z=j-x_{ik}}^{j-y_{ik}} g(b_{ik},z)}{y_{ik}-x_{ik}+1}\right) \\ ex(i,j) &= \frac{g(i,j)}{f(i,j)} \end{align*}$$

The intuitive explanation of the above is that the expected value is the weighted average of the expected value of all possible next states, weighted according to (chance of reaching next state) × (chance of being on time from that state).

This leads immediately to an ~\mathcal{O}((N^2+M)T)~ solution, which can be improved to ~\mathcal{O}((N+M)T)~ by storing the values of ~f~ and ~g~ with a prefix sum array.

Complexity: ~\mathcal{O}((N+M)T)~