UPDATE: I actually managed to hack the Rust Code with this testcase. This is the same as CSES test case #27, but I switch the order of the first two edges. The code fails if it sees the 1 2 -100 edge after the 1 3 1 edge, since that would cause it to traverse the 1 2 -100 edge first (it traverses edges in reverse order of how they show up in the input), and apparently that is enough to make it output 3 instead of the correct answer, -1. As according to CSES Guidelines, all submissions will be regraded. I wonder how this'll turn out!
Problem Summary: Given a directed and weighted graph, find the longest path from node 1 to node N, given that edges can be traversed multiple times. If there is an arbitrarily long path, then print -1. The problem link is here.
My method to solve this problem came straight from the CSES Book: Use the Bellman-Ford Algorithm to determine which nodes (if any) are in a positive cycle. If any positive cycle is reachable from both node 1 and node N, then return -1. Otherwise, just return the longest distance from node 1 to node N. Another method to solve this problem is by using a topological sort and finding the longest distance from node 1 to node N that way.
However, the top-performing code for this problem comes from Rust, and seems to use a completely different method. Here is the code. My main language is C++ so I can kind of interpret some parts of the code. The program seems to keep extra variables first_edge and first_reverse_edge to access edges, instead of using an adjacency list. The function mark_useful_edges() seems to set all edges that can reach node N as useful. But I have no clue how the search() function works.
Can someone interpret this code, or reveal the algorithm or logic the code-writer used?
Note: I understand that simply caring about best performance is a narrow-minded way of learning algorithms. I am interested in this solution because it seems to be a simple way that I have never seen before, and still solves the problem quickly. If this code involves a new technique, I want to learn it.
