• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Jun 27th, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
2. from heapq import heappush, heappop
3.
4. def prim(graph, s):
5.
6.     visited = [False for _ in range(len(graph))]
7.
8.     q = []
9.     heappush(q, (0, s))
10.
11.     tree = 0
12.
13.     while q:
14.         (w, u) = heappop(q)
15.         # precisa ver se e' primeira vez
16.         if not visited[u]:
17.             visited[u] = True
18.             tree += w
19.
20.             for e in graph[u]:
21.                 heappush(q, e)
22.
23.     return tree
24.
25. while True:
26.     n, m = map(int, input().split())
27.     if n == 0 and m == 0:
28.         break
29.
30.     graph = [[] for _ in range(n)]
31.
32.     total = 0
33.     for _ in range(m):
34.         u, v, w = map(int, input().split())
35.         graph[u].append((w, v))
36.         graph[v].append((w, u))
37.         total += w
38.
39.
40.     #for i, es in enumerate(graph):
41.     #    print(i, es)
42.
43.     print(total - prim(graph, 0))
44.     #print(graph)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top