SHARE
TWEET

Untitled

a guest Jun 27th, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # estradas escuras
  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. OK, I Understand
 
Top