There are n cities connected by m flights. Each fight starts from city u and arrives at v with a price w.

Now given all the cities and fights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1.


Example 1:
Input: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
Output: 200
Explanation: 
The graph looks like this:


The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.


Example 2:
Input: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
Output: 500
Explanation: 
The graph looks like this:


The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.

Note:


       The number of nodes n will be in range [1, 100], with nodes labeled from 0 to n - 1.
       The size of flights will be in range [0, n * (n - 1) / 2].
       The format of each flight will be (src, dst, price).
       The price of each flight will be in the range [1, 10000].
       k is in the range of [0, n - 1].
       There will not be any duplicated flights or self cycles.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Shortest paths

Dynamic programming

Data structures

Starter code: class Solution:
    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
        

Solutions:
class Solution:

	def slidingPuzzle(self, board):
		possible_moves = {0: [1, 3], 1: [0, 2, 4], 2: [1, 5], 3: [0, 4], 4: [1, 3, 5], 5: [2, 4]}
		state = ''.join([str(x) for x in board[0]]) + ''.join([str(x) for x in board[1]])
		seen = {state: 0}
		q = [[state, state.find('0')]]
		while q and q[0][0] != '123450':
			cur = q.pop(0)
			for move in possible_moves[cur[1]]:
				new_state = [int(x) for x in cur[0]]
				(new_state[cur[1]], new_state[move]) = (new_state[move], new_state[cur[1]])
				new_state = ''.join([str(x) for x in new_state])
				if new_state not in seen:
					seen[new_state] = seen[cur[0]] + 1
					q.append([new_state, move])
		return -1 if not q else seen[q[0][0]]


class Solution:

	def slidingPuzzle(self, board):
		from collections import deque as dq
		curs = ''.join(map(str, board[0])) + ''.join(map(str, board[1]))
		(dist, pre) = ({}, {})
		dist[curs] = 0
		q = dq([curs])
		while q:
			curs = q.pop()
			if curs == '123450':
				while curs in pre:
					curs = pre[curs]
				return dist['123450']
			ind = curs.index('0')
			if ind > 0 and ind != 3:
				preswap = curs[:ind - 1] + '0' + curs[ind - 1] + curs[ind + 1:]
				if preswap not in dist:
					dist[preswap] = dist[curs] + 1
					pre[preswap] = curs
					q.appendleft(preswap)
			if ind < 5 and ind != 2:
				afterswap = curs[:ind] + curs[ind + 1] + '0' + curs[ind + 2:]
				if afterswap not in dist:
					dist[afterswap] = dist[curs] + 1
					pre[afterswap] = curs
					q.appendleft(afterswap)
			if ind < 3:
				downswap = curs[:ind] + curs[ind + 3] + curs[ind + 1:ind + 3] + '0' + curs[ind + 4:]
				if downswap not in dist:
					dist[downswap] = dist[curs] + 1
					pre[downswap] = curs
					q.appendleft(downswap)
			else:
				upswap = curs[:ind - 3] + '0' + curs[ind - 2:ind] + curs[ind - 3] + curs[ind + 1:]
				if upswap not in dist:
					dist[upswap] = dist[curs] + 1
					pre[upswap] = curs
					q.appendleft(upswap)
		return -1


class Solution:

	def slidingPuzzle(self, board):
		q = collections.deque()
		steps = collections.defaultdict(int)
		start = tuple(board[0] + board[1])
		steps[start] = 0
		q.append(start)
		target = (1, 2, 3, 4, 5, 0)
		while q:
			bd = q.popleft()
			if bd == target:
				return steps[bd]
			ind = bd.index(0)
			(i, j) = (ind // 3, ind % 3)
			for (m, n) in [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]]:
				if 0 <= m < 2 and 0 <= n < 3:
					move = list(bd)
					(move[ind], move[m * 3 + n]) = (move[m * 3 + n], move[ind])
					new_bd = tuple(move)
					if new_bd not in steps or steps[new_bd] > steps[bd] + 1:
						q.append(new_bd)
						steps[new_bd] = steps[bd] + 1
		return -1


class Solution:

	def __init__(self):
		self.win = [[1, 2, 3], [4, 5, 0]]
		self.lose = [[[1, 2, 3], [5, 4, 0]], [[2, 1, 3], [4, 5, 0]], [[1, 3, 2], [4, 5, 0]], [[3, 0, 1], [4, 2, 5]], [[4, 2, 3], [1, 5, 0]], [[1, 5, 3], [4, 2, 0]]]

	def slidingPuzzle(self, board):
		s = 0
		if board == self.win:
			return 0
		to = [board]
		path = [board]
		while True:
			s += 1
			t = []
			for x in to:
				tmp = self.move(x)
				for z in tmp:
					if z not in path:
						path.append(z)
						t.append(z)
			for y in t:
				if y == self.win:
					return s
				else:
					for z in self.lose:
						if z == y:
							return -1
			to = t
		return -1

	def same(self, x, y):
		for i in range(2):
			for j in range(3):
				if x[i][j] != y[i][j]:
					return False
		return True

	def copy(self, x):
		r = []
		for y in x:
			r.append(y.copy())
		return r

	def move(self, bd):
		p = self.find(bd)
		r = []
		low = p[0] > 0
		le = p[1] == 0
		re = p[1] == 2
		if not le:
			to = self.copy(bd)
			to[p[0]][p[1]] = bd[p[0]][p[1] - 1]
			to[p[0]][p[1] - 1] = 0
			r.append(to)
		if not re:
			to = self.copy(bd)
			to[p[0]][p[1]] = bd[p[0]][p[1] + 1]
			to[p[0]][p[1] + 1] = 0
			r.append(to)
		if low:
			to = self.copy(bd)
			to[p[0]][p[1]] = bd[p[0] - 1][p[1]]
			to[p[0] - 1][p[1]] = 0
			r.append(to)
		else:
			to = self.copy(bd)
			to[p[0]][p[1]] = bd[p[0] + 1][p[1]]
			to[p[0] + 1][p[1]] = 0
			r.append(to)
		return r

	def find(self, bd):
		for (i, x) in enumerate(bd):
			if 0 in x:
				return (i, x.index(0))


class Solution:

	def __init__(self):
		self.GOAL_STATE = [1, 2, 3, 4, 5, 0]

	def slidingPuzzle(self, board):
		from itertools import chain
		seen = set()
		from collections import deque
		q = deque()
		q.append((list(chain.from_iterable(board)), 0))
		while q:
			(state, dist) = q.popleft()
			seen.add(tuple(state))
			if state == self.GOAL_STATE:
				return dist
			for nextState in self.nextStates(state):
				if tuple(nextState) not in seen:
					q.append((nextState, dist + 1))
		return -1

	def swap(self, state, i, j):
		temp = state[i]
		state[i] = state[j]
		state[j] = temp

	def getNeighbors(self, index):
		neighbors = {0: [1, 3], 1: [0, 4, 2], 2: [1, 5], 3: [0, 4], 4: [3, 1, 5], 5: [4, 2]}
		return neighbors[index]

	def nextStates(self, state):
		states = []
		zeroIndex = state.index(0)
		for nei in self.getNeighbors(zeroIndex):
			nextState = list(state)
			self.swap(nextState, nei, zeroIndex)
			states.append(nextState)
		return states


class Solution:

	def slidingPuzzle(self, board):
		step = 0
		board = tuple(map(tuple, board))
		q = [board]
		memo = set([board])
		while q:
			q0 = []
			for b in q:
				if b == ((1, 2, 3), (4, 5, 0)):
					return step
				for x in range(2):
					for y in range(3):
						if b[x][y]:
							continue
						for (dx, dy) in zip((1, 0, -1, 0), (0, 1, 0, -1)):
							(nx, ny) = (x + dx, y + dy)
							if 0 <= nx < 2 and 0 <= ny < 3:
								nb = list(map(list, b))
								(nb[x][y], nb[nx][ny]) = (nb[nx][ny], nb[x][y])
								nb = tuple(map(tuple, nb))
								if nb not in memo:
									memo.add(nb)
									q0.append(nb)
			q = q0
			step += 1
		return -1