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 youcanshould 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**_.↵
↵
↵
If you don't know what relaxation means in this context or what the pseudocode of the Bellman-Ford algorithm looks like you
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**_.↵
↵
↵
