py板prim算法

解题思路:

注意事项:注意理解题目的输入用例到底是什么意思

参考代码:

n=int(input())

inf=float('inf')

gra=[[inf for _ in range(n+1)] for _ in range(n+1)]

st=[False]*(n+1)

a=[]

for _ in range(n):

    w=a.append(list(map(int,input().split())))

for i in range(1,n+1):

    for j in range(1,n+1):

        gra[i][j]=a[i-1][j-1]

def prim():

    res=0

    dis=[inf]*(n+1)

    dis[1]=0

    for i in range(n):

        t=-1

        for j in range(1,n+1):

            if st[j]==False and (t==-1 or dis[t]>dis[j]):

                t=j

        if dis[t]==inf:return inf #说明非连通

        res+=dis[t]

        st[t]=True

        for j in range(1,n+1):

            dis[j]=min(dis[j],gra[t][j])

    return res

print(prim())