In contrast to the paths queries under private transportation, which mainly concern the length or the driving time of a path, the paths queries under public transportation have to consider the time sequences between subsequent edges, as well as the total cost over a path. This study looks into three types of queries:given a source node, a destination node, a time interval, and a cost constraint, to find out a path within the given time interval which is restricted by the cost constraint, and has (i) the earliest arrival time, or (ii) the latest departure time, or (iii) the shortest duration. Firstly, a modified Dijkstra's algorithm called Dijk-CCMTP is presented based on derived algorithms respectively for the three types of queries above. After that, an effective indexing structure ACCTL (approximate cost constrained time labelling) is proposed. ACCTL invokes Dijk-CCMTP to precompute some canonical paths from (and, to) each node in the graph. For any query from source node s to destination node d, the approximate answer path can be obtain by matching those canonical paths that are from s (and, to d) in a database table join manner, so as to avoid traversing on the entire graph. The preprocessing time to build ACCTL is O(|V|·△_max·|E|·(log|E|+△_max)), where|V|is the number of nodes,|E|the number of edges, and △_max the maximal degree among the nodes in the graph. Finally, the efficiency and effectiveness of ACCTL are confirmed. Experimental results show that the query algorithm under ACCTL is 2~3 orders of magnitude faster than the Dijkstra variant methods. The index preprocessing time and index size are also analyzed.