Yeah. Of course.

The edges are directed and the cost is not y+x/a1, but (y+x)/a1 - sorry for that.

The intuition behind that is : each number x is in the form k*a1 + l, k and l are integers and l < a1.

Actually it means that x/a1 = k, x mod a1 = l.

Another interesting fact is that if we can reach number x we can reach x + a1 too.

So if we want to find out if number x is in A’ we just check iff distance from 0 to l = x mod a1 is not greater than k = x/a1.

If distance is lower or equal , than x is in the set(A’). If it is greater than x is not in the set.

For example : A = {5,11,14,16}

Than we have 5 vertices because a1 = 5.

0 1 2 3 4

11 = 1 mod 5, 11/5=2

14 = 4 mod 5, 14/5=2

16 = 1 mod 5, 16/5=3

for each pair(element in A, some vertex) - let this pair be (x,y) :

we add an edge with cost (x+y)/a1 from y to (y+x)%a1.

We can omit the edges from a1, because they have no sense at all. (0->0).

From 0 we have 3 edges : 0 -> 1 (cost = 2), 0 -> 4 (cost = 2), 0 -> 1 (cost = 3).

From 1 we have 3 edges : 1 -> 2 (cost = 2), 1 -> 0 (cost = 3), 1 -> 2 (cost = 3).

From 2 we have 3 edges : 2 -> 3 (cost = 2), 2 -> 1 (cost = 3), 2 -> 3 (cost = 3).

From 3 we have 3 edges : 3 -> 4 (cost = 2), 3 -> 2 (cost = 3), 3 -> 4 (cost = 3).

From 4 we have 3 edges : 4 -> 0 (cost = 3), 4 -> 3 (cost = 3), 4 -> 0 (cost = 4).

Than we just run dijkstra from 0.

Distances from 0 :

0 : 0

1 : 2

2 : 4

3 : 6

4 : 2

Now some checking :

x = 11 ? x%5 = 1, x/5 = 2, distance to 1 = 2. 2 <= 2 so it is in set (btw. that was obvious, 11 is in A)

x = 28 ? x%5 = 3, x/5 = 5, distance to 3 = 6. 6 is not less or equal than 5, so 28 is not in A’

I hope it helped.

If not than ask me about the thing you don’t understand.

Don’t forget to rate it and mark it as solved if you liked it.