Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # estradas escuras
- from heapq import heappush, heappop
- def prim(graph, s):
- visited = [False for _ in range(len(graph))]
- q = []
- heappush(q, (0, s))
- tree = 0
- while q:
- (w, u) = heappop(q)
- # precisa ver se e' primeira vez
- if not visited[u]:
- visited[u] = True
- tree += w
- for e in graph[u]:
- heappush(q, e)
- return tree
- while True:
- n, m = map(int, input().split())
- if n == 0 and m == 0:
- break
- graph = [[] for _ in range(n)]
- total = 0
- for _ in range(m):
- u, v, w = map(int, input().split())
- graph[u].append((w, v))
- graph[v].append((w, u))
- total += w
- #for i, es in enumerate(graph):
- # print(i, es)
- print(total - prim(graph, 0))
- #print(graph)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement