Here’s the problem Statement
I understood the question but can’t figure out how to implement it through code. I did read the editorial but it seems quiet complicated.
If anyone can provide a simple and clear implementation of this problem, then that would be really helpful.
The editorial says that it needs bitmasks, but how do I use it here?
Thanks in advance.
1 Like
I agree, the editorial there is quite complicated. Looking for a simpler explanation myself!
Why has the answer been deleted? I don’t understand!
From starting node, to any node we can came up with different set of fish with some minimum cost,
so at each node, 2^K possibility, we will use bitmasking and apply dijkstra’s algorithm,
with one extra states, states(cost , mask , node ) , where mask represent the set of fish.
and instead of single cost array , we will use cost[node][mask] , because at each node ,
we can came up with different-2 set of fish.
And finally, we will calculate our result , by taking all pair combination
of mask , such that (mask1 | mask2 ) contain all K fish , and then out of all
possible valid pairs, we take minimum cost , min(ans , max(cost[n][mask1],cost[n][mask2]))
1 Like