I have two different solutions which handle this test very differently:

20 5
24
0.0 - 1.0
0.1 - 1.0
0.2 - 1.1
0.3 - 1.2
0.4 - 1.3
0.5 - 1.4
0.6 - 1.5
0.7 - 1.6
0.8 - 1.7
0.9 - 1.8
0.10 - 1.9
0.11 - 1.10
0.12 - 1.11
0.13 - 1.12
0.14 - 1.13
0.15 - 1.14
0.16 - 1.15
0.17 - 1.16
0.18 - 1.17
0.18 - 2.0
0.18 - 3.0
0.18 - 4.0
0.18 - 5.0
0.19 - 1.18
0 19

One of them might be even close to TLE, but both my solutions accepted here with time 0.015 s, which makes me think there is no such test in the list of tests.
I think this test should be added...

Let
0,1,2,..N-1     - outer door
N ..  2*N - 1   - 1-inner room doors
2*N .. 3N - 1   - 2-inner room doors
....
i*N  i*N + 1,  .. i*N + N-1   - i-th room doors

total  (K+1)*N  doors.

W[i][j] - minimum dist from i to j-th door, where  0 <= i,j < (K+1)*N

initially  W[i][i] = 0,  W[i][j] = inifinity  for i <> j.

read,  and set W[i][j] = 1   if there exists road from i to j doors.

-----------------
N times run following steps:

1. Floyd algorithm  for 0.. (K+1)*N - 1   doors.

2.
  for  1<= t <= K ,  0 <= i, j < N  update
        W[t*N + i][ t*N + j]  = min(W[t*N + i][t*N+j], W[i][j])
  Because  (t*N + i, t*N + j)  - is identical path as outer  (i,j) path.


Edited by author 31.10.2020 16:46

Hello,

I got WA#6 But for few days I'm unable to find a test that fails for my algorithm.
Does anyone has any hints? I would really appreciate any help.

Di and Do may _COINCIDE_.

Very good problem, thanks to authors!

It took me almost a week to invent the easy solution.
Don't ask how, just think. My test



4 1
4
0.0 - 1.1
0.1 - 1.2
0.2 - 1.3
0.2 - 0.3
0 3

--
7

Don't understand - the algorithm is just Floyd, and so few people solved this problem...