Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link ×

Formal proof for a approach of 877D — Olya and Energy Drinks

Revision en1, by Yuki726, 2019-03-14 22:09:48

In this submission for the problem 31660028 the author used if(ans[ni][nj] < ans[][] + 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).


  Rev. Lang. By When Δ Comment
en4 English Yuki726 2019-03-14 22:14:03 65
en3 English Yuki726 2019-03-14 22:12:03 0 (published)
en2 English Yuki726 2019-03-14 22:11:29 2
en1 English Yuki726 2019-03-14 22:09:48 322 Initial revision (saved to drafts)