SHARE
TWEET

Untitled

a guest Oct 20th, 2019 77 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import heapq
  2.  
  3.  
  4. class Edge():
  5.     def __init__(self, u, v, w):
  6.         self.u = u
  7.         self.v = v
  8.         self.w = w
  9.  
  10.     def __str__(self):
  11.         return str(self.u) + ' ' + str(self.v) + ' ' + str(self.w)
  12.  
  13.  
  14. n = int(input())
  15. m = int(input())
  16.  
  17. adj_list = []
  18.  
  19. for i in range(n):
  20.     adj_list.append([])
  21.  
  22. for i in range(m):
  23.     line = input()
  24.     u = int(line.split(' ')[0])
  25.     v = int(line.split(' ')[1])
  26.     w = int(line.split(' ')[2])
  27.     adj_list[u].append(Edge(u, v, w))
  28.     adj_list[v].append(Edge(v, u, w))
  29.  
  30. num_exit = int(input())
  31. exits = []
  32. for i in range(num_exit):
  33.     exits.append(int(input()))
  34.  
  35. dist = []
  36. sec_dist = []
  37. visited = []
  38. for i in range(n):
  39.     dist.append(500)
  40.     sec_dist.append(500)
  41.     visited.append(0)
  42.     # Set to Infinity = 500
  43.  
  44. pq = []
  45.  
  46. for ex in exits:
  47.     dist[ex] = 0
  48.     sec_dist[ex] = 0
  49.     visited[ex] = 1
  50.     for e in adj_list[ex]:
  51.         alt = dist[e.u] + e.w
  52.         if alt >= 500:
  53.             continue
  54.         if alt < dist[e.v]:
  55.             sec_dist[e.v] = dist[e.v]
  56.             dist[e.v] = alt
  57.             heapq.heappush(pq, (sec_dist[e.v], e.v))
  58.         elif alt < sec_dist[e.v]:
  59.             sec_dist[e.v] = alt
  60.             heapq.heappush(pq, (sec_dist[e.v], e.v))
  61.  
  62.  
  63. while len(pq) > 0:
  64.     tpl = heapq.heappop(pq)
  65.     u = tpl[1]
  66.     if u == 0:
  67.         break
  68.     if visited[u] == 1:
  69.         continue
  70.     visited[u] = 1
  71.     for e in adj_list[u]:
  72.         alt = dist[u] + e.w
  73.         print(e, alt)
  74.         if alt < dist[e.v]:
  75.             sec_dist[e.v] = dist[e.v]
  76.             dist[e.v] = alt
  77.             if sec_dist[e.v] < 500:
  78.                 heapq.heappush(pq, (sec_dist[e.v], e.v))
  79.         elif alt < sec_dist[e.v]:
  80.             sec_dist[e.v] = alt
  81.             heapq.heappush(pq, (sec_dist[e.v], e.v))
  82.  
  83.  
  84. print(sec_dist[0])
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top