my code : pE06ol - Online C++0x Compiler & Debugging Tool - Ideone.com
source : a bit of cs: a bit of graph dp: SPOJ - ROADS
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?
This is my solution:Online Compiler and IDE - GeeksforGeeks
(dont run it in gfg as it cannot allocate that much memory)
If u dont understand,feel free to ask.
If u feel anything wrong,plz tell!!
what is the advantage of running same for loop again? did you done it by mistake or it’s really doing something?
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 )
I think the test cases were weak,it shouldn’t have passed.
However i couldnt find any counter case on it.
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?
because this code isn’t accepted : Spoj : ROADS, C++ (gcc) - rextester
I dont think so any problem should occur,I tried it and got AC,here is my solution: Online Compiler and IDE - GeeksforGeeks
just put this statement in the 2 for loops,
if(i==1)
{
dp[i][j]=0;
continue;
}
u’ll get ac.
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.
my solution: Online Compiler and IDE - GeeksforGeeks
yes, i have seen that but didn’t able to understand the last loop(after all non-zero costs)…last time can you please explain me that?
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.
Hope this clears!!
If u find anything wrong,plz tell.