SPOJ RDNWK: Road Network

Given undirected graph of N nodes, M edges and a ranked list of exciting cities. You are to answer Q queries of the form (u, v, K), asking you to find the cost of the shortest path from u to v such that only the first K cities in the ranked list are allowed as intermediate nodes in the path.

N <= 150, M <= N^2, Q <= 6000