Yuki726's blog

By Yuki726, history, 7 months ago, In English,

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).

Problem Link: https://codeforces.com/problemset/problem/877/D

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Yuki726 (previous revision, new revision, compare).

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Yuki726 (previous revision, new revision, compare).