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

Правка en1, от Anthony_Smith, 2022-04-10 21:39:44

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.

Теги cses, graph, ford-bellman

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский Anthony_Smith 2022-04-17 18:25:16 4 Tiny change: 'est case #11, but I sw' -> 'est case #27, but I sw'
en4 Английский Anthony_Smith 2022-04-16 23:28:20 88
en3 Английский Anthony_Smith 2022-04-16 23:27:45 106
en2 Английский Anthony_Smith 2022-04-16 23:26:52 541
en1 Английский Anthony_Smith 2022-04-10 21:39:44 1717 Initial revision (published)