Consider a vertex having Min(a) (All of them in case of having multiple minimums) and name it "u". The answer for this (those) city is a_i. Lest consider the next minimum (Min₂(a)) and name it "v". There are two cases. it can go to the city having Min₁(a) or just stay there(why?). This property holds for every vertex having Min_i(a). It can go to one of those vertexes having Min_j(a) with j ≤ i.

Now we assume that it's better for vertex "v" to go to vertex "u". on the shortest path from "v" to "u" there is a vertex (call it "x". Of course it can be "v" itself) which is adjacent to "u". It can be easily proved that best answer for vertex "x" would be to go to "u".

So what it means? every time we find the answer for some vertex we can relax all of its neighbors and then we are done with remaining vertex having minimum found answer.

Hi everybody.

Here is my code which uses FFT (Fast Fourier Transform) to solve Task E. It doesn't fit in time and memory limits (works well for ) but it's good for educational purposes. Actually it has time complexity but FFT has a large constant so it takes around 10secs for .

Yes, but I didn't understand the idea behind the code

Sorry! I don't understand why "y" is incremented here if(a[pos] == maxval) x--, y++;