Jul 2019
1 / 6
Jul 2019
Aug 2019
heyjoe
Jul '19
1 
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 < other.key

class Edge:

    def __init__(self, to_vertex, cost):
        self.to_vertex = to_vertex
        self.cost = cost

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 < 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)

    sys.stdout.write("{0}".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):
        vertices_list = list()
        sys.stdin.readline()

        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)

        # MST(vertices_list)
        testcase = TestCase(vertices_list)
        testcases.append(testcase)

    count = 0
    for testcase in testcases:
        MST(testcase.vertices)
        # if count < case_num -1:
        #     print()
        # count = count + 1



if __name__ == "__main__":
    main()

  • created

    Jul '19

  • last reply

    Aug '19
  • 5

    replies

  • 931

    views

  • 2

    users

  • 1

    like

  • 2

    links

simes
Jul '19

You may want to Google Priority Queue.

heyjoe
Jul '19

When I use sort, heapify, it show the same error, time exceeded. That is the one example of how I did it but with normal sort, linear sort and heapq show the same results.

simes
Jul '19

Apologies, I missed that you’d commented out the call to the method I’d highlighted.

Please could you add a link to the problem.

How many vertices are there in the queue? After removing each vertex from the queue, you re-sort the remainder - doesn’t that strike you as expensive?

Here’s a thought or four

  1. Initially, each vertex has a key of infinity. Except for the very first starting vertex, it won’t ever be returned from the queue. So why put it in the queue in the first place? Except for the starting vertex, I’d only add vertices to the queue once I’d visited a vertex with an edge to them.

  2. You can stop processing the queue once you’ve connected all vertices.

  3. If you don’t reduce the distance to any vertex (perhaps because all vertices reachable from the current vertex have previously been visited) then there’s no need to resort the queue.

  4. I’d not keep a queue of vertex objects, but a heap queue of a structure that had a vertex index or pointer or whatever, and its priority (or weight in this case.) This means that each time I want to reduce the key for a vertex, I can simply create another queue object for it, and heappush it. Heappush and heappop maintain the heap structure, so there’s no need to resort the queue each time. This would mean there can be multiple queue entries for a vertex, so item 2 is important, and so is checking whether you’ve already visited a popped vertex so you don’t re-process it.

Note: I don’t know Python, so perhaps I’ve overlooked something important. ymmv.

heyjoe
Jul '19

Thanks. I will try to modify according to your suggestion.