i have tried to code it using the first technique mentioned there but got WA!
one thing i skip is that considering zero cost paths because i think that as we are iterating over all the edges and if the zero edge really help then it would have been reflected in the answer there itself! please help me where i am going wrong?
no it was because of the edge whose cost is 0.Since if an edge cost is 0,for a particular vertex in state i,i would require its adjacent vertex ans in state i(as dp[i][j] would depend on some dp[i][k]),so if we know the kth vertex ans its fine.So i run it two time.
lets say vertices are 1 3 2
where 2’s ans depend on 1,and 3’s ans depend on 2
so in first iteration we have correctly calculated 2’s value,however value of 3 was not calculated correctly.
so in next iterartion since value of 2 is calculated ,3’s ans would be calculated correctly.
Plz see if sth is wrong,(however it got accepted )
one more thing here your dp state is “minimum distance to reach j with atmost k cost” but if i make it something like “minimum dist to reach j with exactly k cost” then what is the problem?
yes this works but can you please explain me why? because as we are saying exactly k cost then why will dp[1][k] = 0 (if k != 0) because we are already at 1. I know i am irritating you but please help me !
yeah ur right,it should have work.I think the 2 for loop method actually causes wa.
I tried another method for handling 0’s and its foolproof(from the source you provided),here basically we handle all non zero edges first and then deal with all pair of zero edges.
for(ll v=0;v<n;++v){
for(ll u=0;u<n;++u){
if(fw[u][v] <pow(10,11)){
dp[i][v] = min(dp[i][u] + fw[u][v], dp[i][v]);
}
}
lets consider a graph such that all its edges are of cost 0,so if we had to calculate the ans for cost 0,it would be same as finding the shortest path from source to all vertices.
If Lets say some vertices are connected by edges of cost 0,and other non zero,so u can say that for all the vertices which actually act as a source for edges of cost 0 are fixed(ie their answer wouldnt change for this cost i during running of above for loop)
So only the answers of those verices will change which acts as destination for an edge with cost 0. Most of confusion comes from this statement:
dp[i][v] = min(dp[i][u] + fw[u][v], dp[i][v]); as u might think that if u werent calculated,v’s ans would be not correct.However if u try it on paper,u’ll see that only the fixed vertices actually cause the ans.So if u know the shortest path from the fixed vertices to v,dp[i][v] is ensured to be correct.For the example i discussed where all edge are 0 cost,u can consider source as the only fixed vertix.
U could try dividing the graph into sub components of 0 cost,(u can move to any vertex to any other accessible vertex in that component at 0 cost),so if u want to reach a node v within that component,first reach the border vertices(fixed vertices) of that component and then from all fixed vertices see the shortest path to v and accordingly update the ans.