Structural colors generated due to light scattering from static all-dielectric metasurfaces have successfully enabled high-resolution, high-saturation and wide-gamut color printing applications. Despite recent advances, most demonstrations of these structure-dependent colors lack post-fabrication tunability that hinders their applicability for front-end dynamic display technologies. Phase-change materials (PCMs), with significant contrast of their optical properties between their amorphous and crystalline states, have demonstrated promising potentials in reconfigurable nanophotonics. Herein, we leverage a tunable all-dielectric reflective metasurface made of a newly emerged class of low-loss optical PCMs with superb characteristics, i.e., antimony trisulphide (Sb$_2$S$_3$), antimony triselenide (Sb$_2$Se$_3$), and binary germanium-doped selenide (GeSe$_3$), to realize switchable, high-saturation, high-efficiency and high-resolution structural colors. Having polarization sensitive building blocks, the presented metasurface can generate two different colors when illuminated by two orthogonally polarized incident beams. Such degrees of freedom (i.e., structural state and polarization) enable a single reconfigurable metasurface with fixed geometrical parameters to generate four distinct wide-gamut colors suitable for a wide range of applications, including tunable full-color printing and displays, information encryption, and anti-counterfeiting.