We study the renormalization of the gap of an s-wave superconductor in the presence of two magnetic impurities. For weakly bound Shiba states, we analytically calculate the part of the gap renormalization that is sensitive to the relative orientation of the two impurity spins. For impurities with a strong exchange coupling to the conduction electrons, we solve the gap equation self-consistently by numerics and find that the subgap Shiba state turns into a supragap Andreev state when the local gap parameter changes sign under the impurities.