There are n cities and m edges connected by some number of flights. You are given an array flights where flights[i] = [from_{i}, to_{i}, price_{i}] indicates that there is a flight from the city from_{i} to city to_{i} with cost price_{i}.
You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.
 
Note: The price from city A to B may be different From price from city B to A. 
Example 1:
Input:
n = 4
flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]]
src = 0
dst = 3
k = 1
Output:
700
Explanation:
The optimal path with at most 1 stop from city 0 to 3 is marked in red and has cost 100 + 600 = 700.
Note that the path through cities [0,1,2,3] is cheaper but is invalid because it uses 2 stops.
Constraint:
1 <= n <= 100
0 <= flights.length <= (n * (n - 1) / 2)
flights[i].length == 3
0 <= from_{i}, to_{i} < n
from_{i} != to_{i}
1 <= price_{i} <= 10^{4}
There will not be any multiple flights between the two cities.
0 <= src, dst, k < n
src != dst

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3

from typing import List



class Solution:

    def CheapestFLight(self,n,flights,src,dst,k):

        pass





Solutions:
import queue
from typing import List

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		dist = [float('inf')] * n
		adjList = {}
		for i in range(n):
			adjList[i] = []
		for i in flights:
			u = i[0]
			v = i[1]
			price = i[2]
			adjList[u].append([v, price])
		s = queue.Queue()
		starting_stop = 0
		starting_price = 0
		s.put([starting_stop, starting_price, src])
		while not s.empty():
			(stop, price, node) = s.get()
			if stop > k:
				break
			for i in adjList[node]:
				adjNode = i[0]
				curr_price = i[1]
				net_price = price + curr_price
				if net_price < dist[adjNode]:
					s.put([stop + 1, net_price, adjNode])
					dist[adjNode] = net_price
		if dist[dst] == float('inf'):
			return -1
		return dist[dst]


from typing import List
from math import inf

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):

		def adjListCreator(n, flights):
			adjList = {i: [] for i in range(0, n)}
			for node in flights:
				(source, destination, price) = node
				adjList[source].append((destination, price))
			return adjList

		def cheapestFlight(source, dest, k, adjList, n):
			distance = [inf for i in range(0, n)]
			distance[source] = 0
			queue = []
			queue.append((0, source, 0))
			while queue:
				(stops, node, dist) = queue.pop(0)
				if stops > k:
					continue
				for neighbour in adjList[node]:
					adjNode = neighbour[0]
					edW = neighbour[1]
					if dist + edW < distance[adjNode] and stops <= k:
						distance[adjNode] = dist + edW
						queue.append((stops + 1, adjNode, distance[adjNode]))
			if distance[dest] == inf:
				return -1
			return distance[dest]
		return cheapestFlight(src, dst, k, adjListCreator(n, flights), n)


from typing import List
import heapq
import math

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		graph = [[] for i in range(n)]
		minHeap = [(0, src, k + 1)]
		dist = [[math.inf] * (k + 2) for _ in range(n)]
		for (u, v, w) in flights:
			graph[u].append((v, w))
		while minHeap:
			(d, u, stops) = heapq.heappop(minHeap)
			if u == dst:
				return d
			if stops > 0:
				for (v, w) in graph[u]:
					newDist = d + w
					if newDist < dist[v][stops - 1]:
						dist[v][stops - 1] = newDist
						heapq.heappush(minHeap, (newDist, v, stops - 1))
		return -1


from typing import List

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		distances = [float('inf') for i in range(n)]
		distances[src] = 0
		iterations = k + 1
		for i in range(iterations):
			temp = distances.copy()
			for (s, d, w) in flights:
				if distances[s] != float('inf'):
					if distances[s] + w < temp[d]:
						temp[d] = distances[s] + w
			distances = temp
		if distances[dst] == float('inf'):
			return -1
		return distances[dst]


from typing import List

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		distances = [float('inf')] * n
		distances[src] = 0
		for _ in range(k + 1):
			temp = distances[:]
			for (s, d, w) in flights:
				if distances[s] != float('inf') and distances[s] + w < temp[d]:
					temp[d] = distances[s] + w
			distances = temp
		if distances[dst] == float('inf'):
			return -1
		return distances[dst]


from typing import List
from collections import defaultdict, deque

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		path = defaultdict(list)
		for (u, v, w) in flights:
			path[u].append((v, w))
		q = deque()
		dist = [float('inf')] * n
		dist[src] = 0
		q.append((0, src, 0))
		while q:
			(stops, node, cost) = q.popleft()
			if stops > k:
				continue
			for (adjNode, adjW) in path[node]:
				if cost + adjW < dist[adjNode] and stops <= k:
					dist[adjNode] = cost + adjW
					q.append((stops + 1, adjNode, cost + adjW))
		return dist[dst] if dist[dst] != float('inf') else -1


from collections import defaultdict as dq
from queue import PriorityQueue as Pq
from typing import List

class Solution:

	def CheapestFLight(self, n, arr, s, des, k):
		ds = dq(list)
		q = Pq()
		for i in arr:
			ds[i[0]].append([i[1], i[2]])
		dist = [float('inf')] * n
		dist[s] = 0
		q.put([0, -1, s])
		while not q.empty():
			node = q.get()
			dCurr = -node[0]
			stations = node[1]
			curr = node[2]
			for j in ds[curr]:
				ind = j[0]
				disJ = j[1]
				if dist[ind] > disJ + dCurr and stations + 1 <= k:
					dist[ind] = disJ + dCurr
					q.put([-(disJ + dCurr), stations + 1, ind])
		if dist[des] == float('inf'):
			return -1
		return dist[des]


from typing import List
from collections import defaultdict, deque
import sys

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		adjList = defaultdict(list)
		for edge in flights:
			adjList[edge[0]].append((edge[1], edge[2]))
		dist = [sys.maxsize for i in range(n)]
		queue = deque()
		queue.append((0, src, 0))
		dist[src] = 0
		while queue:
			(stops, node, dis) = queue.popleft()
			if stops > k:
				continue
			for edge in adjList[node]:
				nextNode = edge[0]
				nextDist = edge[1]
				if dis + nextDist < dist[nextNode]:
					dist[nextNode] = dis + nextDist
					queue.append((stops + 1, nextNode, dist[nextNode]))
		if dist[dst] == sys.maxsize:
			return -1
		return dist[dst]


from typing import List
import heapq
from heapq import *

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		distance = [1000000000.0] * n
		graph = [[] for i in range(n)]
		for (u, v, w) in flights:
			graph[u].append((v, w))
		distance[src] = 0
		minHeap = [(0, src, 0)]
		while minHeap:
			(stop, node, weight) = heapq.heappop(minHeap)
			if stop > k:
				continue
			for i in graph[node]:
				new_node = i[0]
				new_weight = i[1]
				if weight + new_weight < distance[new_node] and k >= stop:
					distance[new_node] = weight + new_weight
					heapq.heappush(minHeap, (stop + 1, new_node, distance[new_node]))
		return -1 if distance[dst] == 1000000000.0 else distance[dst]


from typing import List
from collections import defaultdict

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		d = defaultdict(list)
		for i in flights:
			d[i[0]].append([i[1], i[2]])
		dist = [999999999] * n
		dist[src] = 0
		q = []
		q.append((0, src, 0))
		while q:
			(stop, node, cost) = q.pop(0)
			if stop > k:
				continue
			for it in d[node]:
				adjnode = it[0]
				dis = it[1]
				if dist[adjnode] > dis + cost and stop <= k:
					dist[adjnode] = cost + dis
					q.append((stop + 1, adjnode, dist[adjnode]))
		if dist[dst] == 999999999:
			return -1
		else:
			return dist[dst]


from typing import List
import heapq

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		mini = 999999
		adj = []
		dist = []
		for i in range(n):
			adj.append([])
			dist.append(999999)
		for i in range(len(flights)):
			adj[flights[i][0]].append([flights[i][2], flights[i][1]])
		q = [(0, 0, src)]
		dist[src] = 0
		count = 0
		while len(q) != 0:
			node = heapq.heappop(q)
			if node[2] == dst and node[0] <= k + 1:
				mini = min(mini, node[1])
			if node[0] > k:
				continue
			for i in adj[node[2]]:
				a = dist[i[1]]
				dist[i[1]] = node[1] + i[0]
				if a != dist[i[1]] and node[0] <= k:
					heapq.heappush(q, (node[0] + 1, node[1] + i[0], i[1]))
		if mini == 999999:
			return -1
		return mini


from typing import List
import heapq

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		dist = [int(1000000000.0) for _ in range(n)]
		dist[src] = 0
		for _ in range(k + 1):
			temp = dist.copy()
			for f in flights:
				dist[f[1]] = min(dist[f[1]], temp[f[0]] + f[2])
		return -1 if dist[dst] == int(1000000000.0) else dist[dst]


from typing import List
import heapq

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		pq = []
		g = [[] for _ in range(n)]
		for f in flights:
			g[f[0]].append((f[1], f[2]))
		dist = [[-1 for _ in range(k + 2)] for _ in range(n)]
		dist[src][0] = 0
		pq.append((0, 0, src))
		ans = -1
		while len(pq) > 0:
			(price, stop, v) = heapq.heappop(pq)
			if v == dst:
				if ans == -1 or ans > price:
					ans = price
			if stop > k:
				continue
			for (w, weight) in g[v]:
				if dist[w][stop + 1] == -1 or dist[w][stop + 1] > price + weight:
					dist[w][stop + 1] = price + weight
					heapq.heappush(pq, (dist[w][stop + 1], stop + 1, w))
		return ans


from typing import List
import sys

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		q = []
		adj = [[] for _ in range(n)]
		for i in range(len(flights)):
			u = flights[i][0]
			v = flights[i][1]
			wt = flights[i][2]
			adj[u].append([v, wt])
		distance = [float('inf')] * n
		distance[src] = 0
		q = [[0, src, 0]]
		while q:
			(fare, row, stop) = q.pop(0)
			if stop > k:
				continue
			for (v, wt) in adj[row]:
				if stop <= k and distance[v] > fare + wt:
					q.append([fare + wt, v, stop + 1])
					distance[v] = fare + wt
		if distance[dst] == float('inf'):
			return -1
		else:
			return distance[dst]


from typing import List
import sys

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		dist = [float('inf')] * n
		adj = [[] for i in range(n)]
		for i in flights:
			adj[i[0]].append([i[1], i[2]])
		q = [[0, src, 0]]
		while q:
			s = q.pop(0)
			fare = s[0]
			row = s[1]
			stop = s[2]
			if stop > k:
				continue
			for i in adj[row]:
				if stop <= k and dist[i[0]] > fare + i[1]:
					q.append([fare + i[1], i[0], stop + 1])
					dist[i[0]] = fare + i[1]
		if dist[dst] == float('inf'):
			return -1
		else:
			return dist[dst]


from typing import List
from heapq import *

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		graph = []
		for i in range(n):
			graph.append([])
		for i in flights:
			graph[i[0]].append([i[1], i[2]])
		d = [float('inf')] * n
		stops = [float('inf')] * n
		minheap = []
		d[src] = 0
		heappush(minheap, (0, 0, src))
		stops[src] = 0
		while minheap:
			(dist, stop, vertex) = heappop(minheap)
			if vertex == dst:
				return dist
			if stop == k + 1:
				continue
			for (v, w) in graph[vertex]:
				new_distance = dist + w
				new_stop = stop + 1
				if new_distance < d[v]:
					d[v] = new_distance
					stops[v] = new_stop
					heappush(minheap, (d[v], stops[v], v))
				elif new_stop < stops[v]:
					heappush(minheap, (new_distance, new_stop, v))
		return -1


from typing import List
import heapq as h

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		adj = [[] for i in range(n)]
		for (u, v, d) in flights:
			adj[u].append((v, d))
		pq = [(0, src, 0)]
		dist = [float('inf')] * n
		dist[src] = 0
		h.heapify(pq)
		stop = 0
		while pq:
			(stop, node, d) = h.heappop(pq)
			for (v, price) in adj[node]:
				s = stop
				if dist[v] > price + d:
					s += 1
					if s <= k + 1:
						dist[v] = price + d
						h.heappush(pq, (s, v, dist[v]))
		if k + 1 >= stop and dist[dst] != float('inf'):
			return dist[dst]
		return -1


from typing import List
from collections import deque

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		paths = [[] for _ in range(n)]
		for (start, end, cost) in flights:
			paths[start].append((end, cost))
		queue = deque([(0, src, 0)])
		dis = [float('inf') for _ in range(n)]
		dis[src] = 0
		while queue:
			(stops, root, cost) = queue.popleft()
			if stops > k:
				continue
			for (node, wt) in paths[root]:
				if cost + wt < dis[node] and stops <= k:
					dis[node] = cost + wt
					queue.append((stops + 1, node, dis[node]))
		if dis[dst] == float('inf'):
			return -1
		return dis[dst]


from typing import List
from collections import deque, defaultdict

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		q = deque()
		adj = defaultdict(list)
		for (s, e, w) in flights:
			adj[s].append((e, w))
		dist = [1000000000.0] * n
		dist[src] = 0
		q.append((0, (src, 0)))
		while q:
			it = q.popleft()
			stop = it[0]
			node = it[1][0]
			cost = it[1][1]
			if stop > k:
				continue
			for nei in adj[node]:
				neigh = nei[0]
				edw = nei[1]
				if edw + cost < dist[neigh] and stop <= k:
					dist[neigh] = edw + cost
					q.append((stop + 1, (neigh, dist[neigh])))
		if dist[dst] == 1000000000.0:
			return -1
		return dist[dst]


from typing import List

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		prices = [float('inf')] * n
		prices[src] = 0
		for i in range(k + 1):
			tmpPrices = prices.copy()
			for (s, d, p) in flights:
				if prices[s] == float('inf'):
					continue
				if prices[s] + p < tmpPrices[d]:
					tmpPrices[d] = prices[s] + p
			prices = tmpPrices
		return -1 if prices[dst] == float('inf') else prices[dst]


from typing import List
from heapq import heappop, heappush
from math import inf
inf = float('inf')

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		adj = [[] for _ in range(n)]
		for (u, v, price) in flights:
			adj[u].append((v, price))
		q = []
		q.append((0, (src, 0)))
		dist = [inf for _ in range(n)]
		dist[src] = 0
		while q:
			item = heappop(q)
			stops = item[0]
			node = item[1][0]
			cost = item[1][1]
			if stops > k:
				continue
			for (item, price) in adj[node]:
				if stops <= k:
					if dist[item] > price + cost:
						dist[item] = price + cost
						heappush(q, (stops + 1, (item, price + cost)))
		if dist[dst] != inf:
			return dist[dst]
		return -1


from typing import List
from collections import *
import heapq

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		graph = defaultdict(list)
		for (i, j, w) in flights:
			graph[i].append((j, w))
		visited = {}
		qu = [(0, 0, src)]
		while qu:
			(cost, stops, node) = heapq.heappop(qu)
			if node == dst and stops - 1 <= k:
				return cost
			if node not in visited or visited[node] > stops:
				visited[node] = stops
				for (nei, wt) in graph[node]:
					heapq.heappush(qu, (cost + wt, stops + 1, nei))
		return -1


from typing import List
from queue import Queue

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		adj = [[] for i in range(n)]
		for flight in flights:
			adj[flight[0]].append((flight[1], flight[2]))
		dist = [1000000000.0 for i in range(n)]
		dist[src] = 0
		q = Queue()
		q.put((0, src, 0))
		mincost = 1000000000.0
		while not q.empty():
			(step, node, distance) = q.get()
			if node == dst:
				mincost = min(mincost, distance)
			for u in adj[node]:
				if dist[u[0]] > dist[node] + u[1] and step + 1 <= k + 1:
					dist[u[0]] = distance + u[1]
					q.put((step + 1, u[0], dist[u[0]]))
		if mincost != 1000000000.0:
			return mincost
		return -1


from typing import List
from collections import defaultdict
from heapq import heappush, heappop

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		graph = defaultdict(list)
		for (u, v, w) in flights:
			graph[u].append([v, w])
		heap = []
		heappush(heap, [0, src, k + 1])
		visited = [0] * n
		while heap:
			(price, node, remain_k) = heappop(heap)
			if node == dst and remain_k >= 0:
				return price
			if visited[node] > remain_k:
				continue
			visited[node] = remain_k
			for (nei, nei_price) in graph[node]:
				heappush(heap, [price + nei_price, nei, remain_k - 1])
		return -1


from typing import List
import collections
from collections import deque
import math

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		pass
		q = collections.deque()
		q.append((0, 0, src))
		adj = []
		for i in range(n):
			adj.append([])
		for i in range(len(flights)):
			adj[flights[i][0]].append([flights[i][1], flights[i][2]])
		dis = []
		for i in range(n):
			dis.append(math.inf)
		dis[src] = 0
		while q:
			a = q.popleft()
			(s, d, n) = a
			for i in adj[n]:
				(x, y) = (i[0], i[1])
				if dis[x] > d + y and s <= k:
					dis[x] = d + y
					q.append((s + 1, dis[x], x))
		if dis[dst] == math.inf:
			return -1
		return dis[dst]


from typing import List
import heapq

class Solution:

	def CheapestFLight(self, n, flights, src, dst, k):
		adj = [[] for i in range(n)]
		for (i, j, w) in flights:
			adj[i].append([j, w])

		def djs():
			q = []
			heapq.heapify(q)
			dist[src][0] = 0
			heapq.heappush(q, (0, src, 0))
			while q:
				(d, node, p) = heapq.heappop(q)
				if p > k + 1 or node == dst:
					continue
				for (i, w) in adj[node]:
					if p + 1 < k + 2 and d + w < dist[i][p + 1]:
						dist[i][p + 1] = d + w
						heapq.heappush(q, (d + w, i, p + 1))
		dist = [[float('inf') for i in range(k + 2)] for j in range(n)]
		djs()
		if dist[dst][-1] == float('inf'):
			return -1
		return dist[dst][-1]