Can someone interpret the top-performing Rust code for CSES Graph Theory: High Score?

Revision en3, by Anthony_Smith, 2022-04-16 23:27:45

UPDATE: I actually managed to hack the Rust Code with this testcase. This is the same as CSES test case #11, but I switch the order of the first two edges. This 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). 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.

Tags cses, graph, ford-bellman

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English Anthony_Smith 2022-04-17 18:25:16 4 Tiny change: 'est case #11, but I sw' -> 'est case #27, but I sw'
en4 English Anthony_Smith 2022-04-16 23:28:20 88
en3 English Anthony_Smith 2022-04-16 23:27:45 106
en2 English Anthony_Smith 2022-04-16 23:26:52 541
en1 English Anthony_Smith 2022-04-10 21:39:44 1717 Initial revision (published)