| # | User | Rating |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3831 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | gamegame | 3386 |
| 10 | ksun48 | 3373 |
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 164 |
| 1 | maomao90 | 164 |
| 3 | Um_nik | 163 |
| 4 | atcoder_official | 160 |
| 5 | -is-this-fft- | 158 |
| 6 | awoo | 157 |
| 7 | adamant | 156 |
| 8 | TheScrasse | 154 |
| 8 | nor | 154 |
| 10 | Dominater069 | 153 |
Rethink the Dijkstra algorithm -- Let's go deeper
For a long time I think the Dijkstra algorithm (dij) only has two usages:
(1) Calculate the distance between the vertices when the weights of edges are non-negative.
(2) (Minimax) Given a path $$$p = x_1x_2...x_n$$$, define $$$f(p) := \max_{i=1}^{n-1}d(x_i, x_{i+1})$$$. Given source vertex $$$s$$$ and target vertex $$$t$$$, dij is able to calculate $$$min \{f(p)|p \in s-t\,paths\}$$$
| Rev. | Lang. | By | When | Δ | Comment | |
|---|---|---|---|---|---|---|
| en77 |
|
CristianoPenaldo | 2022-10-10 16:15:01 | 19 | ||
| en76 |
|
CristianoPenaldo | 2022-10-10 15:20:42 | 6 | ||
| en75 |
|
CristianoPenaldo | 2022-10-10 15:13:56 | 2 | ||
| en74 |
|
CristianoPenaldo | 2022-10-10 15:09:57 | 110 | (published) | |
| en73 |
|
CristianoPenaldo | 2022-10-10 15:08:00 | 31 | (saved to drafts) | |
| en72 |
|
CristianoPenaldo | 2022-10-10 13:37:13 | 2 | ||
| en71 |
|
CristianoPenaldo | 2022-10-10 13:34:11 | 3 | ||
| en70 |
|
CristianoPenaldo | 2022-10-10 13:32:43 | 0 | (published) | |
| en69 |
|
CristianoPenaldo | 2022-10-10 13:32:19 | 36 | (saved to drafts) | |
| en68 |
|
CristianoPenaldo | 2022-10-10 13:31:17 | 530 | (published) | |
| en67 |
|
CristianoPenaldo | 2022-10-10 13:25:58 | 127 | ||
| en66 |
|
CristianoPenaldo | 2022-10-10 13:24:03 | 172 | ||
| en65 |
|
CristianoPenaldo | 2022-10-10 13:14:11 | 426 | ||
| en64 |
|
CristianoPenaldo | 2022-10-10 13:09:47 | 138 | ||
| en63 |
|
CristianoPenaldo | 2022-10-10 13:06:14 | 92 | ||
| en62 |
|
CristianoPenaldo | 2022-10-10 13:05:30 | 82 | ||
| en61 |
|
CristianoPenaldo | 2022-10-10 12:47:38 | 207 | ||
| en60 |
|
CristianoPenaldo | 2022-10-10 12:42:59 | 566 | ||
| en59 |
|
CristianoPenaldo | 2022-10-10 12:28:21 | 807 | ||
| en58 |
|
CristianoPenaldo | 2022-10-10 12:26:11 | 43 | ||
| en57 |
|
CristianoPenaldo | 2022-10-10 12:24:29 | 12 | Tiny change: 'nature of operator$+$, it satis' -> 'nature of add, it satis' | |
| en56 |
|
CristianoPenaldo | 2022-10-10 12:24:00 | 339 | ||
| en55 |
|
CristianoPenaldo | 2022-10-10 12:20:57 | 58 | ||
| en54 |
|
CristianoPenaldo | 2022-10-10 12:16:51 | 2 | Tiny change: 'g order:\n- 6, 4, 4, 2' -> 'g order:\n6, 4, 4, 2' | |
| en53 |
|
CristianoPenaldo | 2022-10-10 12:12:54 | 142 | ||
| en52 |
|
CristianoPenaldo | 2022-10-10 12:11:43 | 105 | ||
| en51 |
|
CristianoPenaldo | 2022-10-10 12:09:29 | 106 | ||
| en50 |
|
CristianoPenaldo | 2022-10-10 12:08:00 | 98 | ||
| en49 |
|
CristianoPenaldo | 2022-10-10 12:04:51 | 58 | ||
| en48 |
|
CristianoPenaldo | 2022-10-10 12:02:01 | 390 | ||
| en47 |
|
CristianoPenaldo | 2022-10-10 11:51:36 | 341 | ||
| en46 |
|
CristianoPenaldo | 2022-10-10 11:35:49 | 594 | ||
| en45 |
|
CristianoPenaldo | 2022-10-10 11:24:49 | 4 | Tiny change: '], k = 5\nOutput: 2\nExplanat' -> '], k = 5\n\nOutput: 2\n\nExplanat' | |
| en44 |
|
CristianoPenaldo | 2022-10-10 11:24:13 | 636 | ||
| en43 |
|
CristianoPenaldo | 2022-10-10 11:11:57 | 785 | ||
| en42 |
|
CristianoPenaldo | 2022-10-10 10:55:25 | 65 | ||
| en41 |
|
CristianoPenaldo | 2022-10-10 10:53:30 | 393 | ||
| en40 |
|
CristianoPenaldo | 2022-10-10 10:40:51 | 1009 | ||
| en39 |
|
CristianoPenaldo | 2022-10-10 10:32:56 | 467 | ||
| en38 |
|
CristianoPenaldo | 2022-10-10 10:09:51 | 457 | ||
| en37 |
|
CristianoPenaldo | 2022-10-10 10:03:10 | 172 | ||
| en36 |
|
CristianoPenaldo | 2022-10-10 10:00:37 | 244 | ||
| en35 |
|
CristianoPenaldo | 2022-10-10 09:43:49 | 554 | ||
| en34 |
|
CristianoPenaldo | 2022-10-10 09:41:27 | 75 | ||
| en33 |
|
CristianoPenaldo | 2022-10-10 09:35:29 | 148 | ||
| en32 |
|
CristianoPenaldo | 2022-10-10 09:32:55 | 199 | ||
| en31 |
|
CristianoPenaldo | 2022-10-10 09:30:42 | 233 | ||
| en30 |
|
CristianoPenaldo | 2022-10-10 09:28:01 | 354 | ||
| en29 |
|
CristianoPenaldo | 2022-10-10 09:25:05 | 231 | ||
| en28 |
|
CristianoPenaldo | 2022-10-10 09:19:41 | 359 | ||
| en27 |
|
CristianoPenaldo | 2022-10-10 09:09:04 | 183 | ||
| en26 |
|
CristianoPenaldo | 2022-10-10 09:06:18 | 171 | ||
| en25 |
|
CristianoPenaldo | 2022-10-10 09:02:53 | 62 | ||
| en24 |
|
CristianoPenaldo | 2022-10-10 09:00:04 | 93 | ||
| en23 |
|
CristianoPenaldo | 2022-10-10 08:58:11 | 5 | ||
| en22 |
|
CristianoPenaldo | 2022-10-10 08:57:48 | 25 | ||
| en21 |
|
CristianoPenaldo | 2022-10-10 08:56:55 | 42 | ||
| en20 |
|
CristianoPenaldo | 2022-10-10 08:55:49 | 78 | ||
| en19 |
|
CristianoPenaldo | 2022-10-10 08:55:04 | 37 | ||
| en18 |
|
CristianoPenaldo | 2022-10-10 08:53:59 | 223 | ||
| en17 |
|
CristianoPenaldo | 2022-10-10 08:51:11 | 514 | ||
| en16 |
|
CristianoPenaldo | 2022-10-10 08:41:54 | 179 | ||
| en15 |
|
CristianoPenaldo | 2022-10-10 08:38:13 | 212 | ||
| en14 |
|
CristianoPenaldo | 2022-10-10 08:35:32 | 142 | ||
| en13 |
|
CristianoPenaldo | 2022-10-10 08:19:16 | 31 | Tiny change: 'ion base) For **every** source point $s \in S$, ' -> 'ion base) $\forall s \in S$, ' | |
| en12 |
|
CristianoPenaldo | 2022-10-10 08:18:55 | 165 | ||
| en11 |
|
CristianoPenaldo | 2022-10-10 08:14:54 | 208 | ||
| en10 |
|
CristianoPenaldo | 2022-10-10 08:11:52 | 514 | ||
| en9 |
|
CristianoPenaldo | 2022-10-10 08:04:15 | 82 | ||
| en8 |
|
CristianoPenaldo | 2022-10-10 08:02:43 | 66 | ||
| en7 |
|
CristianoPenaldo | 2022-10-10 08:01:19 | 380 | ||
| en6 |
|
CristianoPenaldo | 2022-10-10 07:56:08 | 3 | Tiny change: ' \\{f(p)|p \text{is a' -> ' \\{f(p)|p\,\text{is a' | |
| en5 |
|
CristianoPenaldo | 2022-10-10 07:55:58 | 14 | Tiny change: '\{f(p)|p \in s-t\,paths\\}$\n' -> '\{f(p)|p \text{is a s-t path}\\}$\n' | |
| en4 |
|
CristianoPenaldo | 2022-10-10 07:55:32 | 1 | Tiny change: 's-t\,paths}\\}$\n' -> 's-t\,paths\\}$\n' | |
| en3 |
|
CristianoPenaldo | 2022-10-10 07:55:20 | 16 | Tiny change: 'n \\{f(p)|$p$ \text {is a s-t path}\\}$\n' -> 'n \\{f(p)|p \in s-t\,paths}\\}$\n' | |
| en2 |
|
CristianoPenaldo | 2022-10-10 07:54:52 | 191 | Tiny change: 'p) := \min$\n' -> 'p) := \min_{i=1}^{n-1}d(x_i, x_{i+1})$\n' | |
| en1 |
|
CristianoPenaldo | 2022-10-10 06:49:27 | 243 | Initial revision (saved to drafts) |
