글 읽기 - 파이썬 프림 알고리즘..(9%에서 틀렸습니다..)

lms062111 2년 전 0

반례들은 거의 다 맞는데 왜 틀린지 잘 모르겠습니다..

'''
내용:백준 알고리즘 단계별 풀기 최소 신장 트리 1197
날짜:21년4월28일
사용 언어:파이썬
'''

import sys
import heapq

v, e = map(int,sys.stdin.readline().rstrip().split())
adjlist = [[] for _ in range(v+1)]
cost = [sys.maxsize for _ in range(v+1)]
cost[1] = 0
isInMST = [False for _ in range(v+1)]
E = [None for _ in range(v+1)]
mst = 0
for _ in range(e):
    a, b, c =  map(int,sys.stdin.readline().rstrip().split())
    adjlist[a].append((b,c))
    adjlist[b].append((a,c))

heap = []

for i in range(1,v+1):
    heapq.heappush(heap,(cost[i],i))

while heap:
    cost_, v = heapq.heappop(heap)
    isInMST[v] = True

    if E[v] != None:
        mst += cost_

    for w, c in adjlist[v]:
        if not isInMST[w] and c < cost[w]:
            heap.remove((cost[w],w))
            cost[w] = c
            E[w] = v
            heapq.heappush(heap,(cost[w],w))

print(mst)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬 프림 알고리즘..(9%에서 틀렸습니다..)

lms062111 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말