In recent years, many of the location-based services provide information of a single type of spatial objects, based on their spatial closeness to the query object. However, in real-life applications, user may be interested in obtaining information about different types of objects (e.g., hotels, restaurants, and theaters), in terms of their neighboring relationship. Moreover, an important aspect that has not been previously explored is the total cost of experiencing various types of spatial objects. As a result, we present a new type of location-based queries, named the minimum total cost query (MTCQ), which takes both the neighboring relationship and the total experiencing cost of spatial objects into account. Given the n types of spatial objects and a user-defined distance d, the MTCQ finds a set of n objects such that the distance between any pair of objects does not exceed d and their total cost is smallest. To efficiently process the MTCQ, we utilize an R-tree-based index, the Rc-tree, to manage the spatial objects with their locations and costs. Then, two processing algorithms, namely the top-k-based MTCQ algorithm and the enhanced MTCQ algorithm, are proposed to determine a set of objects satisfying the constraint of distance d, whose total cost is lowest. Finally, extensive experiments using the synthetic dataset are conducted to demonstrate the efficiency and the effectiveness of the proposed algorithms.