Minimum penalty path

#1

how to solve this problem …plz provide code and expalination…
i want to solve it using bfs…

#2

This is the code https://ide.codingblocks.com/s/239134

#3

The approach is that we can reach any vertex and it can have 1024 possible values of OR, i.e the cost of reaching it. So we start bfs from source vertex and start with initial OR equal to 0, now if we take an edge, cost to travel along that edge would be (initial cost | current weight of edge),but we need to only push that sequence into the queue if we had not visited this node before with same cost.

I am talking about this part in the code

for (size_t j = 0; j < g[ver].size(); j++) {
int to = g[ver][j].F;
int add = g[ver][j].S;
if (!used[to][(add | res_or)]) {
used[to][(add | res_or)] = true;
q.push(mp(to, (add | res_or)));
}
}

After this bfs, code is self explanatory

#4

How 1024 possible values??

#5

The edge weight can be from 1 to 1023, so it is actually 1023 values.
So choose any subset of integers in this ranges , do their bitwise or, ans lies from 1 to 1023

#6

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.