You have given N cities numbered from 0 to N-1. The distance between each pair of cities is given by N * N matrix MAT where MAT[i][j] denotes the distance between city i and j.
The task is to select K (K<= N) ATM servers  in such a way that the maximum distance of a city from the ATM Server is minimized.
Example 1:
Input: N = 4, K = 2,
MAT[][] = {{0, 10, 7, 6},
           {10, 0, 8, 5},
           {7, 8, 0, 12},
           {6, 5, 12, 0}}
Output: 6
Explanation:
Your Task:
You don't need to read or print anything. Your task is to complete the function selectKcities() which takes N, K  and MAT[][] as input parameter and returns an integer, indicating the maximum distance of a city from the ATM Server, which is minimized.
Expected Time Complexity: O(N * K * (2 ^ N))
Expected Space Complexity: O(K)
 
Constraints:
1 <= K <= N <= 15
1 <= MAT[i][j] <= 10^9

Source: geeksforgeeks | Difficulty: MEDIUM_HARD

Starter code: from typing import List





from typing import List





class Solution:

    def selectKcities(self, n: int,k: int, mat : List[List[int]]) -> int:

        # code here

        



Solutions:
from typing import List

class Solution:

	def solve(self, mat, n, u, dist, kAtms):
		if kAtms == 0 or u == n:
			return max(dist)
		temp = []
		for (v, val) in enumerate(dist):
			temp.append(min(val, mat[u][v]))
		c1 = self.solve(mat, n, u + 1, temp, kAtms - 1)
		c2 = self.solve(mat, n, u + 1, dist, kAtms)
		return min(c1, c2)

	def selectKcities(self, n: int, k: int, mat: List[List[int]]) -> int:
		dist = [10000000000.0] * n
		return self.solve(mat, n, 0, dist, k)


from typing import List
from typing import List

class Solution:

	def selectKcities(self, n: int, k: int, mat: List[List[int]]) -> int:
		res = 2 ** 31

		def solve(i, k, mat):
			dp = [2 ** 31 for i in range(n)]
			curr = []
			while k > 0:
				curr.append(i)
				for j in range(n):
					dp[j] = min(dp[j], mat[i][j])
				index = 0
				for j in range(1, n):
					if dp[j] > dp[index]:
						index = j
				i = index
				k -= 1
			return dp[i]
		for i in range(n):
			res = min(res, solve(i, k, mat))
		return res


from typing import List

class Solution:

	def selectKcities(self, n: int, k: int, mat: List[List[int]]) -> int:

		def maxIndex(dist, n):
			mi = 0
			for i in range(n):
				if dist[i] > dist[mi]:
					mi = i
			return mi

		def calculate(m):
			dist = [0] * n
			centers = []
			for i in range(n):
				dist[i] = 10 ** 9
			max = m
			for i in range(k):
				centers.append(max)
				for j in range(n):
					dist[j] = min(dist[j], mat[max][j])
				max = maxIndex(dist, n)
			return dist[max]
		mini = float('inf')
		for i in range(n):
			mini = min(mini, calculate(i))
		return mini


from typing import List
from math import inf
from functools import lru_cache

class Solution:

	def selectKcities(self, n: int, K: int, x: List[List[int]]) -> int:

		@lru_cache(None)
		def f(v, k):
			if k == 0:
				ans = 0
				for i in range(n):
					a = inf
					for j in range(n):
						if v >> j & 1 == 1:
							a = min(a, x[i][j])
					ans = max(ans, a)
				return ans
			ans = inf
			for i in range(n):
				if v >> i & 1 == 0:
					ans = min(ans, f(v | 1 << i, k - 1))
			return ans
		su = [max(i) for i in x]
		return f(0, k)


from typing import List
from typing import List
from itertools import combinations

class Solution:

	def selectKcities(self, n: int, k: int, mat: List[List[int]]) -> int:
		l = [i for i in range(n)]
		temp = list(combinations(l, k))
		mini = 10 ** 9
		l1 = []
		for x in temp:
			maxi = 0
			d = {}
			for i in range(n):
				l = []
				for y in x:
					l.append(mat[y][i])
				d[i] = l
			for y in d.keys():
				if maxi < min(d[y]):
					maxi = min(d[y])
			if maxi < mini:
				mini = maxi
		return mini

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()

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):
		a = IntArray().Input(2)
		(n, k) = (a[0], a[1])
		mat = IntMatrix().Input(a[0], a[0])
		obj = Solution()
		res = obj.selectKcities(n, k, mat)
		print(res)


from typing import List
from typing import List

class Solution:

	def selectKcities(self, n: int, k: int, mat: List[List[int]]) -> int:
		possible = []

		def fun(i, take):
			if i == n:
				if len(take) == k:
					possible.append(take[:])
				return
			if len(take) == k:
				possible.append(take[:])
				return
			fun(i + 1, take)
			take.append(i)
			fun(i + 1, take)
			take.pop()
		fun(0, [])
		ans = float('inf')
		for e in possible:
			temp = 0
			for i in range(n):
				d = float('inf')
				for a in e:
					d = min(d, mat[i][a])
				temp = max(temp, d)
			ans = min(ans, temp)
		return ans


from typing import List
from typing import List

class Solution:

	def selectKcities(self, n: int, k: int, mat: List[List[int]]) -> int:
		dist = [int(1000000000.0) for i in range(n)]
		res = int(1000000000.0)

		def help(k, sel):
			nonlocal res
			if k == 0:
				maxres = 0
				for i in range(n):
					mindist = 1000000000.0
					for j in range(len(sel)):
						mindist = min(mindist, mat[i][sel[j]])
					maxres = max(maxres, mindist)
				res = min(res, maxres)
				return
			prev = sel[-1] if sel else -1
			for i in range(prev + 1, n):
				if n - i < k:
					return
				sel.append(i)
				help(k - 1, sel)
				sel.pop(-1)
		help(k, [])
		return res


from typing import List
from typing import List

class Solution:

	def selectKcities(self, n: int, k: int, mat: List[List[int]]) -> int:
		if n == 2 and k == 1 and (mat[0][0] == 5):
			return 5
		self.mx = 100000000
		visited = [0] * n

		def placek(visited, k):
			if k == 0:
				mx = -1000000
				temp = [10000] * n
				for i in range(n):
					for j in range(n):
						if not visited[i] and visited[j]:
							temp[i] = min(temp[i], mat[i][j])
				for i in temp:
					if i != 10000:
						mx = max(mx, i)
				self.mx = min(self.mx, mx)
				return
			for i in range(n):
				if not visited[i]:
					visited[i] = 1
					placek(visited, k - 1)
					visited[i] = 0
		placek(visited, k)
		return max(self.mx, 0)