In this paper, we present the first optimal hybrid quantum-classical algorithm for the many-agent pathfinding (MAPF) problem. MAPF is a problem of determining collision-free paths for multiple agents to reach a goal location in a shared space, which becomes computationally difficult especially when dealing with a large number of agents. In this paper, we present a hybrid algorithm based on branch-and-cut-and-price and integrate quantum computing (QC) into the iterative solution of the QUBO problem based on a conflict graph. We demonstrate that it outperforms the existing QUBO formulation and the state-of-the-art MAPF solver through experiments on real quantum hardware and benchmark data.