In problem 316C2, the solution is to find Max Flow Min Cost of the constructed graph.
Skimming through some fastest submissions, I noticed that there is a function called modify_label that replaced SPFA to find shortest path in normal MFMC. Here is one of those submisions.
And this modify_label only cost $$$O(|V| + |E|)$$$ complexity, result in small overall complexity. I think this has some relation with Johnson's algorithm.
Please someone explained it to me how this function works and how this is applicable with this problem. Thanks :<.
From what I see it seems to be an implementation of something called ‘ZKW min cost flow’, which is a combination of Dinic style flow augmentation and potential distance updates. AFAIK it works well on networks with small costs (which is the case with your problem) and short augmenting paths(?), but I’m not exactly sure how well (the article I read at that time was Google translated Chinese).
Maybe this might help? https://www.programmersought.com/article/27296528787/
Thanks <3