状压dp（蓝桥杯补给）(python)

旅行商的变种题，区别在于经历过的地点还可以过去，所以动态转移方程为：

dp[i][state]=min(dp[j][sub]+dis[i][j]) if state&(1<

其中，sub 是 (1<

Python真的离谱， 跑啥都跑不过去，慢死 ，只跑了50%

code:

import copy

n,d=map(int,input().split())
l=[]
for o in range(n):
    mid=list(map(int,input().split()))
    l.append(mid[:])
def ji(x1,y1,x2,y2):
    return ((x1-x2)**2+(y1-y2)**2)**0.5
inf=float('inf')
dis=[[inf for i in range(n)]for i in range(n)]
for   i in range(n):
    for j in range(i+1,n):
        ans=ji(l[i][0],l[i][1],l[j][0],l[j][1])
        if ans<=d:
            dis[i][j]=dis[j][i]=ans


def dj(s,e):
    if s==e:
        return 0
    visit=copy.deepcopy(dis[s])
    visited=[0]*n
    visited[s]=1

    ind=s
    while True:
        mid = inf
        for i in range(n):
            if visited[i]==0 and visit[i]< mid:
                mid=visit[i]
                ind=i
        if ind==e:
            return visit[ind]

        visited[ind]=1
        for j in range(n):
            if visited[j] ==0 and visit[j]>visit[ind]+dis[ind][j]:
                visit[j] = visit[ind] + dis[ind][j]
dp=[[0 for i in range(1<