Formal proof for a approach of 877D — Olya and Energy Drinks 
Разница между en3 и en4, 65 символ(ов) изменены
In this submission for the problem [submission: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).↵
↵
Problem Link: https://codeforces.com/problemset/problem/877/D↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский Yuki726 2019-03-14 22:14:03 65
en3 Английский Yuki726 2019-03-14 22:12:03 0 (published)
en2 Английский Yuki726 2019-03-14 22:11:29 2
en1 Английский Yuki726 2019-03-14 22:09:48 322 Initial revision (saved to drafts)