Is Dijkstra's overrated????
Разница между en1 и en2, 9 символ(ов) изменены
Recently I got accepted on the [Shortest Routes I](https://cses.fi/problemset/task/1671) problem from the [CSES problemset](https://cses.fi/problemset/list/) using the **Bellman-Ford** algorithm.↵
If you don't know what relaxation means in this context or what the pseudocode of the Bellman-Ford algorithm looks like you 
canshould study the algorithm before continuing the reading.↵
Here's my idea for solving the problem↵
--------------------------------------↵
Firstly, I applied the typical optimization when all the edge weights in the given graph are positive, which involves stopping the algorithm once no relaxation operation occurs during an iteration.↵
After getting TLE in 6 cases I thought in a way of ordering the edges in order to take advantage of the latter optimization.↵
Finally, I deleted multi-edges(storing just the lowest weight of the repeted edges) and in a very intuitive manner I run a BFS from the source( node 1 in this case) and I sorted the edges in the same order the BFS had visited them (including back edges).↵
Surprisingly, It passed the tests!!!!↵

I'm wondering if someone could be so gentle of hacking [my solution](https://cses.fi/paste/56b942b47666376d7be871/) or explain me why it works.↵
I don't know how to filter by name in the **hacking** page of the CSES website in a certain problem, however, you can find my submission if you go to the hacking tab in the [Shortest Routes I](https://cses.fi/problemset/task/1671) problem and then sort by maximum runnung time, my submission shows up in the 4th page with a max runtime of 0.95 seconds with the username Victor_Luis123.↵
_**Thanks in advance**_.↵


История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Victor_Luis123 2024-01-09 07:39:51 9 Tiny change: ' like you can study the' -> ' like you should study the'
en1 Английский Victor_Luis123 2024-01-09 04:54:54 1668 Initial revision (published)