In this submission for the problem 31660028 the author used if(ans[ni][nj] < ans[v.fi][v.se] + 1) break;
condition. Can anyone guide me in proving that this algorithm with the break condition produces shortest paths and its complexity is O(n*m).
Formal proof for a approach of 877D — Olya and Energy Drinks
In this submission for the problem 31660028 the author used if(ans[ni][nj] < ans[v.fi][v.se] + 1) break;
condition. Can anyone guide me in proving that this algorithm with the break condition produces shortest paths and its complexity is O(n*m).