There are n cities connected by some number of cars. You are given an array of cars where cars[i] =[from_{i},to_{i},cost_{i}] indicates that there is a car 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.
Example 1:
Input:
N=4
cars =  {{ 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 graph is shown above. The optimal path with at most 1 stops from cities 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.
 
Example 2:
Input:
N = 3
cars = {{0,1,100},{1,2,100},{0,2,500}}
src = 0
dst = 2
k = 1
Output:
200
Explanation:
The graph is shown above. The optimal path with at most 1 stops from city 0 to 2 is marked in red and has cost 100 + 100 = 200.
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minimumCost() which takes a number of cities N, the cars array cars[], the integer src, the integer dst, and the number of stops k as input parameters and returns the minimum cost else -1.
 
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{2}
0<= edges[i][0],edges[i][1] 1<=edges[i][2]<=10^{4}
0<=src,dst,k src!=dst

Source: geeksforgeeks | Difficulty: EASY

Starter code: from typing import List





class Solution:

    def minimumCost(self, n : int, src : int, dst : int, k : int, m : int, cars : List[List[int]]) -> int:

        # code here

        



Solutions:
from typing import List

class Solution:

	def minimumCost(self, n: int, src: int, dst: int, k: int, m: int, cars: List[List[int]]) -> int:
		d = {}
		for i in range(n):
			d[i] = []
		for i in cars:
			d[i[0]].append([i[1], i[2]])
		v = [10 ** 9 for i in range(n)]
		v[src] = 0
		q = [[src, 0, 0]]
		while q:
			(pos, wt, cnt) = q.pop()
			for i in d[pos]:
				if wt + i[1] < v[i[0]]:
					if cnt <= k:
						v[i[0]] = i[1] + wt
						q.append([i[0], wt + i[1], cnt + 1])
		if v[dst] == 10 ** 9:
			return -1
		return v[dst]


from typing import List
from heapq import heappush, heappop

class Node:

	def __init__(self, node, val, stops):
		self.pos = node
		self.cost = val
		self.stops = stops

	def __lt__(self, other):
		return self.cost < other.cost

class Solution:

	def minimumCost(self, n: int, src: int, dst: int, k: int, m: int, cars: List[List[int]]) -> int:
		distance = [float('inf')] * n
		distance[src] = 0
		for i in range(k + 1):
			temp = [vl for vl in distance]
			for i in cars:
				u = i[0]
				v = i[1]
				w = i[2]
				if temp[v] > distance[u] + w:
					temp[v] = distance[u] + w
			distance = [vl for vl in temp]
		if distance[dst] == float('inf'):
			return -1
		return distance[dst]


from typing import List
from heapq import heappush, heappop

class Node:

	def __init__(self, node, val, stops):
		self.pos = node
		self.cost = val
		self.stops = stops

	def __lt__(self, other):
		return self.cost < other.cost

class Solution:

	def minimumCost(self, n: int, src: int, dst: int, k: int, m: int, cars: List[List[int]]) -> int:
		distance = [float('inf')] * n
		distance[src] = 0
		for i in range(k + 1):
			temp = [vl for vl in distance]
			for i in cars:
				u = i[0]
				v = i[1]
				w = i[2]
				if temp[v] > distance[u] + w:
					temp[v] = distance[u] + w
			distance = [vl for vl in temp]
		if distance[dst] == float('inf'):
			return -1
		return distance[dst]

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		src = int(input())
		dst = int(input())
		k = int(input())
		m = int(input())
		cars = IntMatrix().Input(m, m)
		obj = Solution()
		res = obj.minimumCost(n, src, dst, k, m, cars)
		print(res)


from typing import List

class Solution:

	def minimumCost(self, n: int, src: int, dst: int, k: int, m: int, cars: List[List[int]]) -> int:
		distance = [float('inf') for i in range(n)]
		distance[src] = 0
		for i in range(k + 1):
			temp = distance.copy()
			for (x, y, w) in cars:
				temp[y] = min(temp[y], distance[x] + w)
			distance = temp
		return distance[dst] if distance[dst] != float('inf') else -1


from typing import List

class Solution:

	def minimumCost(self, n: int, src: int, dst: int, k: int, m: int, cars: List[List[int]]) -> int:
		dist = [100000000 for i in range(n)]
		dist[src] = 0
		for i in range(k + 1):
			temp = [p for p in dist]
			for it in cars:
				u = it[0]
				v = it[1]
				w = it[2]
				if temp[v] > dist[u] + w:
					temp[v] = dist[u] + w
			dist = [l for l in temp]
		if dist[dst] == 100000000:
			return -1
		return dist[dst]