Need Help! IN CSES Graph Series in Shortest Route 2 problem it is accepting solution of floyd warshall algorithm while O(n*2logn) not (using dijkastra Priority queue).
#
I want to know , when It is benificial to use floyd warshall algorithm and when not ?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 154 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 146 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 133 |
| 10 | cry | 130 |
If $$$O(n^3)$$$ is allowed then it is very short to code floyd warshall. Also, floyd warshall works with negative edges too.
You can check this problem, which uses the idea used in floyd warshall.
Floyd-warshall finds the shortest path from all $$$i$$$ to $$$j$$$ in which internal nodes $$$\in (1, 2, \cdots, k)$$$. Here $$$i, j, k$$$ has the same meaning as described here
Your dijkstra code's complexity would be O(n*m*logn + q) rather than O(n^2*logn), so it will give TLE for the given constraints.