Finding the shortest path between a start and target point on uneven terrain is a fundamental challenge with applications in robotics, gaming, and more. While many existing works have studied efficient shortest path computation, most assume the robot can move unrestricted across the terrain, ignoring mobility constraints. In this paper, we focus on outdoor environments where different types of robots have varying abilities to navigate slopes, depending on their design. We formulate this as the Slope-Constrained Shortest Path Problem (SSPP) on uneven terrain. To efficiently solve the SSPP, we extend the Compressed Path Database, a state-of-the-art shortest path algorithm for grid maps, to create the Slope-Constrained Compressed Path Database (SCPD), which accounts for slope constraints. To improve this, we introduce SCPD-A*, which integrates A* search to refine path quality while retaining fast query times. Experimental results show that our methods significantly outperform the baseline A* algorithm, offering significant improvements in speed and while ensuring high-quality paths.