# @param {Integer} n # @param {Integer[][]} flights # @param {Integer} src # @param {Integer} dst # @param {Integer} k # @return {Integer} def find_cheapest_price(n, flights, src, dst, k) inf=1<<128 min_dist=[inf]*n min_dist[src]=0 (k+1).times do mdp=min_dist.dup flights.each do|i,j,v| mdp[j]=[min_dist[i]+v,mdp[j]].min end min_dist=mdp.dup end ddist=min_dist[dst] return -1 if ddist>=inf ddist end