kssp library

I`ve tried to solve CSES task "visiting cities"

Looks like you can use kind of brute-force - get 1st shortest paths, then all remained with the same cost and make union of cities in each path - nor elegant nor smart algorithm, just to estimate if this approach works at all

I remember from my university course "graph theory" about Yen`s algo to get K-th shortest path so choosed to use some ready (and hopefully well-tested) implementation - kssp library from INRIA (yep - famous place where OCaml was invented)

And then happened real madness - different algos gave me different result and moreover - they didn't match with "correct" results from CSES! Lets see what I got (all results for test 7, compilation options -O3 -DTIME -DNDEBUG):

• Yen - 470s, 30157 cities
• node classification - 4.37s, 30140 cities
• postponed node classification - 3.83s, 30140 cities
• postponed node classification with star - 3.76s, 30140 cities
• sidetrack based - consumed 13Gb of memory and met with OOM killer
  
• parsimonious sidetrack based - OOM again, perhaps bcs not enough parsimonious :-)
  

Source code