백준 문제풀이
백준 16991 - 외판원 순회 3 [Python]
Vermeil
2021. 4. 28. 08:16
16991번: 외판원 순회 3
첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 도시의 좌표 x, y가 주어진다. 모든 좌표는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 두 도시의 위치가 같은 경우
www.acmicpc.net
DP using bitfield
외판원 순회 1과 똑같은 문제이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
import sys
from math import sqrt
input = sys.stdin.readline
INF = 12345678
dp = [[-1 for _ in range(1<<16)] for _ in range(16)]
a = [[0 for _ in range(16)] for _ in range(16)]
b = []
def getDist(a1,a2):
return sqrt((a1[0] - a2[0])*(a1[0] - a2[0]) + (a1[1] - a2[1])*(a1[1] - a2[1]))
def f(now, bit):
if bit == (1<<n)-1:
if a[now][0]: return a[now][0]
return INF
if dp[now][bit] != -1: return dp[now][bit]
dp[now][bit] = INF
for i in range(n):
if bit&(1<<i)==0 and a[now][i] != 0:
dp[now][bit] = min(dp[now][bit], f(i, bit|(1<<i)) + a[now][i])
return dp[now][bit]
n = int(input())
for i in range(n):
b.append(list(map(int, input().split())))
for i in range(n):
for j in range(n):
if i==j: continue
a[i][j] = getDist(b[i], b[j])
print(f(0,1))
|
cs |
