The size of the set k may be exponential but if you have a decision function D(C) == 1 iff there exists a path of cost < C you can use that function to do a binary search over all k's in polynomial time because binary search is log time.
Each call to D should give you 1 bit of the solution and with n bits you can represent numbers from 0 to O(2^n).
Each call to D should give you 1 bit of the solution and with n bits you can represent numbers from 0 to O(2^n).