title: MST challenge gives "time exceeded" error
body: <p>I am doing the <a href="https://www.spoj.com/problems/BLINNET/" rel="nofollow noreferrer">BLINNET problem on <em>Sphere Online Judge</em></a> where I need to find the cost of a minimum spanning tree. I should follow a structure with <code>Edge</code> and <code>Vertex</code> instances. Vertices represent cities in this case. </p>
  
  <p>I get a "time exceeded" error, and I feel like too many <code>for</code> loop iterations are at the cause, but that is the best I can do. I want to try the binary sort to see if it works with that, but that is not easy as it should be sorted using the <code>key</code> property in the <code>City</code> class.</p>
  
  <h3>Sample input</h3>
  
  <pre><code>2
  
  4
  gdansk
  2
  2 1
  3 3
  bydgoszcz
  3
  1 1
  3 1
  4 4
  torun
  3
  1 3
  2 1
  4 1
  warszawa
  2
  2 4
  3 1
  
  3
  ixowo
  2
  2 1
  3 3
  iyekowo
  2
  1 1
  3 7
  zetowo
  2
  1 3
  2 7
  </code></pre>
  
  <h3>Output for the Sample</h3>
  
  <pre><code>3
  4
  </code></pre>
  
  <h2>My code</h2>
  
  <pre><code>import sys
  import heapq
  
  class City:
  
      def __init__(self, city_id):
          self.city_id = city_id
          self.key = float('inf')
          self.parent = None
          self.edge_list = list()
          self.visited = False
          #self.city_name = None
  
      def is_not_visited(self):
          if self.visited is False:
              return True
          return False
  
      def add_neighbor(self, edge):
          self.edge_list.append(edge)
  
      def __lt__(self, other):
          return self.key &lt; other.key
  
  class Edge:
  
      def __init__(self, to_vertex, cost):
          self.to_vertex = to_vertex
          self.cost = cost
  
  #
  # def find_and_pop(queue):
  #     min = queue[0]
  #     index = 0
  #     for a in range(0, len(queue)):
  #         if queue[a].key &lt; min.key:
  #             min = queue[a]
  #             index = a
  #     return queue.pop(index)
  #
  
  def MST(vertices_list):
      queue = vertices_list
      current = queue[0]
      current.key = 0
      #visited_list = list()
      #heapq.heapify(queue)
      total_weight = 0
      while queue:
          #current = find_and_pop(queue)
          current = queue.pop(0)
          for edge in current.edge_list:
              if edge.to_vertex.is_not_visited():
                  if edge.cost &lt; edge.to_vertex.key:
                      edge.to_vertex.key = edge.cost
                      edge.to_vertex.parent = current
          total_weight = total_weight + current.key
          current.visited = True
          queue = sorted(queue, key=lambda x: x.city_id)
          #heapq.heapify(queue)
          #visited_list.append(current)
  
      # total_weight = 0
      # for x in visited_list:
      #     total_weight = total_weight + x.key
      sys.stdout.write("{0}\n".format(total_weight))
  
  class TestCase:
      def __init__(self, vertices):
          self.vertices = vertices
  
  testcases = []
  
  def main():
  
      case_num = int(sys.stdin.readline())
      #skip_line = sys.stdin.readline()
      for n_case in range(0, case_num):
          sys.stdin.readline()
          vertices_list = list()
          number_of_city = int(sys.stdin.readline())
          #interate and make for the time of number of cities
          for n_city in range(0, number_of_city):
              city = City(n_city)
              vertices_list.append(city)
  
          for n_city in range(0, number_of_city):
              c_name = sys.stdin.readline()
              #vertices_list[n_city].city_name = c_name
              num_neighbor = int(sys.stdin.readline())
              for n_neigh in range(0, num_neighbor):
                  to_city_cost = sys.stdin.readline()
                  to_city_cost = to_city_cost.split(" ")
                  to_city = int(to_city_cost[0])
                  cost = int(to_city_cost[1])
                  edge = Edge(vertices_list[to_city-1], cost)
                  vertices_list[n_city].edge_list.append(edge)
  
          testcase = TestCase(vertices_list)
          testcases.append(testcase)
  
      count = 0
      for testcase in testcases:
          MST(testcase.vertices)
          # if count &lt; case_num -1:
          #     print()
          # count = count + 1
  
  
  
  if __name__ == "__main__":
      main()
  </code></pre>