https://www.acmicpc.net/problem/17182

행성끼리 거리가 주어지고, k부터 해서 모든 행성을 가는 가장 짧은 거리를 구하는 문제이다.

플로이드 워셜로 각 행성별 최단거리를 구하고 백트레킹으로 최단거리로 모든 행성 탐사하는 거리를 구했다.

Python

n, k = map(int, input().split())
p = list(list(map(int, input().split())) for _ in range(n))

for t in range(n):
  for i in range(n):
    for j in range(n):
      p[i][j] = min(p[i][j], p[i][t] + p[t][j])

visited = [False] * n
result = 10 * 1000 * 1000
  
def recursive(pos, cnt, cost):
    global result

    if cnt == n:
        result = min(result, cost)
        return

    for next in range(n):
        if not visited[next]:
            visited[next] = True
            recursive(next, cnt + 1, cost + p[pos][next])
            visited[next] = False

visited[k] = True
recursive(k, 1, 0)
print(result)

플로이드 워셜을 제대로 써본 것이 처음이라 나중에 다시 풀어봐야겠다.