Advertisement
Guest User

Untitled

a guest
Oct 22nd, 2016
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.26 KB | None | 0 0
  1. rounds = int(raw_input().strip())
  2.  
  3. for i in range(rounds):
  4. data = map(int, raw_input().strip().split(' '))
  5.  
  6.  
  7. for i in range(data[2]):
  8. pageIdxs.append(int(raw_input().strip())/data[1])
  9.  
  10.  
  11.  
  12.  
  13.  
  14.  
  15. class Graph:
  16. def __init__(self):
  17. self.nodes = set()
  18. self.edges = defaultdict(list)
  19. self.distances = {}
  20.  
  21. def add_node(self, value):
  22. self.nodes.add(value)
  23.  
  24. def add_edge(self, from_node, to_node, distance):
  25. self.edges[from_node].append(to_node)
  26. self.edges[to_node].append(from_node)
  27. self.distances[(from_node, to_node)] = distance
  28.  
  29.  
  30. def dijsktra(graph, initial):
  31. visited = {initial: 0}
  32. path = {}
  33.  
  34. nodes = set(graph.nodes)
  35.  
  36. while nodes:
  37. min_node = None
  38. for node in nodes:
  39. if node in visited:
  40. if min_node is None:
  41. min_node = node
  42. elif visited[node] < visited[min_node]:
  43. min_node = node
  44.  
  45. if min_node is None:
  46. break
  47.  
  48. nodes.remove(min_node)
  49. current_weight = visited[min_node]
  50.  
  51. for edge in graph.edges[min_node]:
  52. weight = current_weight + graph.distance[(min_node, edge)]
  53. if edge not in visited or weight < visited[edge]:
  54. visited[edge] = weight
  55. path[edge] = min_node
  56.  
  57. return visited, path
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement