백준 17182. 우주 탐사선

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

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

# 플로이드-와샬 알고리즘 적용
for k in range(n):
    for i in range(n):
        for j in range(n):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

ans = float('inf')
visited = [0] * n
visited[k] = 1

def dfs(cur, cost, visited_cnt):
    global ans

    # 모든 노드를 방문한 경우
    if visited_cnt == n:
        ans = min(ans, cost)
        return

    # 현재 노드에서 다른 노드로 이동
    for nxt in range(n):
        if not visited[nxt]:  # 방문하지 않은 노드라면
            visited[nxt] = 1
            dfs(nxt, cost + dp[cur][nxt], visited_cnt + 1)
            visited[nxt] = 0  # 백트래킹

# 시작 노드에서 탐색
dfs(k, 0, 1)
print(ans)