sorry,I didn't read carefully.

pretests must be weak, then someone can hack!

but I think it should be strong enough to not see somebody hacks about 15 people on one problem!

Maybe not. Problem statement did not look clear. The last line says "It is guaranteed that the Vanya's Codehorses password is equal to some of his n passwords."

I had done wrongly thought Dijkstra on {cities not visited, time} could work. It took me a lot of time to realise I was wrong.

Because if we pick the smallest abs number, we will waste a minimum number of operations to swap its signal. These operations will only reduce the abs value of our product or increase it by a smaller value than if we used the operation to increase other value, so we dont want to do a lot of these operations because we want to maximize the abs product (and have an odd amount of negative numbers so the signal of the product is negative and then the total product is the minimum)

Consider that you have two elements a_i and a_j, |a_i| < |a_j|. Let m be the smallest number of operations required to change the sign of a_j. If you apply them to a_j, you will get two numbers, a_i and new a_j, and now |a_j| (the new one)  = m·x - |a_j|. If you apply all those m operations to a_i instead (there might be some better ways, but let's consider this), there will be new a_i: |a_i| (the new one)  = m·x - |a_i|, and a_j will remain unchanged. |a_j| > |a_i|, m·x - |a_i| > m·x - |a_j|, and you need to maximize the absolute value of product, so you get a worse situation if you change an element with non-minimum absolute value.

Sure.

Let's consider, for example, a DAG with 6 vertices: v₁, v₂, v₃, v₄, v₅, v₆.
The goal is to arrange all vertices in layers or floors. Let's stick to floors.
Imagine there is a 6-storey building:
[ floor 6 ]
[ floor 5 ]
[ floor 4 ]
[ floor 3 ]
[ floor 2 ]
[ floor 1 ]

Floors somehow (we don't know yet how) correspond to vertices in a graph. We only know the identity of 2 vertices: v₁ is [ floor 1 ] and v₆ is [ floor 6 ], because we always gain access to all of the verices in a graph from vertex v₁ (we always gain access to the floors of a building through the first floor) and we end our travel in a graph in vertex v₆ (we cannot move further up from the floor 6).
Now, we base our decisions about correspondance of vertices v₂, v₃, v₄, v₅ and floors on the fact that if v₂ is some [ floor i] then all of the outgoing edges from v₂ should point to higher floors. That is, once we are on the [ floor 4 ], the floors [ floor 1 ], [ floor 2 ], [ floor 3 ] become blocked for us — we cannot move to these floors from the current [ floor 4 ] by using outgoing edges of current vertex.

At first we have some unordered set of vertices {1, 2, 3, 4, 5, 6}. Then we use topological sort to create an ordered set of vertices with the specified property (we cannot move down from higher floors). Formally, topological sort is a map:
{1, 2, 3, 4, 5, 6} (1, 4, 2, 3, 5, 6).

Below is a graphical representation of that mapping ( topological sort ).

The distinctive property of the picture from the right is that all of the edges are looking to the right. None of the edges look to the left (backwards). Not a single child is pointing to a parent. That means, when you reach vertex v[i] as you go from left to right, there is no way you can update the state of v[i] later as you continue moving to the right.

Actually, the graph on the right is an abstract representation of the concept of dynamic programming. We consider sequence of vertices 1 → 4 → 2 → 3 → 5 → 6 in the specified order. When we are standing on the vertex v[i] it has optimal property (in our case time to travel to that vertex). We update from that vertex v[i] all of it's children. The next vertex in a sequence after v[i] now also has optimal property, because it was updated by parents which had optimal property themselves.

All of that brings us to a conclusion that after we do topological sort we can just look into each of 10 edges (only once) in the following order:

1. 1 → 4
2. 1 → 2
3. 4 → 2
4. 4 → 3
5. 2 → 3
6. 2 → 5
7. 2 → 6
8. 3 → 5
9. 3 → 6
10. 5 → 6