import sys def floyd_warshall(n, graph): # 모든 정점 쌍 간의 최단 경로를 구하기 위한 플로이드 워샬 알고리즘 dist = [row[:] for row in graph] # 그래프 복사 # 갈 수 없는 경로(0)를 큰 값으로 변경 (자기 자신으로 가는 경로는 제외) for i in range(n): for j in range(n): if i != j and dist[i][j] == 0: dist[i][j] = float('inf') # 플로이드 워샬 알고리즘 적용 for k in range(n): for i in range(n): for j in range(n): if dist[i][k] != float('inf') and dist[k][j] != float('inf'): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) return dist def tsp_dp(n, graph): # DP 테이블 초기화 INF = float('inf') dp = [[INF] * (1 << n) for _ in range(n)] # 시작 도시를 0번으로 설정 dp[0][1] = 0 # 0번 도시만 방문한 상태 # 모든 방문 상태에 대해 계산 for visited in range(1, 1 << n): for current in range(n): # 현재 도시가 방문 상태에 포함되어 있지 않으면 스킵 if not (visited & (1 << current)): continue # 이전 상태 계산 prev_visited = visited & ~(1 << current) # 현재 상태가 시작점만 방문한 경우 건너뛰기 if prev_visited == 0: continue # 다음 방문할 도시 결정 for prev in range(n): # 이전 도시가 방문 상태에 포함되어 있지 않거나 갈 수 없는 경로라면 스킵 if not (prev_visited & (1 << prev)) or graph[prev][current] == INF: continue # DP 테이블 업데이트 dp[current][visited] = min( dp[current][visited], dp[prev][prev_visited] + graph[prev][current] ) # 모든 도시를 방문한 후 시작 도시로 돌아가는 최소 비용 계산 all_visited = (1 << n) - 1 result = INF for last in range(1, n): # 마지막 도시는 시작 도시(0)가 아닌 도시 if graph[last][0] != INF: # 마지막 도시에서 시작 도시로 돌아갈 수 있는 경우에만 result = min(result, dp[last][all_visited] + graph[last][0]) return result # 입력 받기 n = int(input()) graph = [] for _ in range(n): graph.append(list(map(int, input().split()))) # 플로이드 워샬 알고리즘으로 최단 경로 계산 shortest_paths = floyd_warshall(n, graph) # TSP 해결 result = tsp_dp(n, shortest_paths) print(result)

제출 #59384

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: