Seems to be similar to a scheduling problem, which I have no experience with. How do you compare the weights between each mercenary while keeping in mind that you cannot alternate back to a previous mercenary?

I have a hunch that this would be vaguely similar to running a modified Dijkstra's algorthm on an singlely linked list that is absurdly interconnected with K starting nodes and K ending nodes.

So far, I've only made a basic solution that always chooses the lowest option available, but that does not take into account that a mercenary may have a better streak of low cost options latter on.