Untitled

mail@pastecode.io avatar
unknown
plain_text
10 months ago
1.3 kB
5
Indexable
Never
import heapq. Χ

def order(city_nodes, city_from, city_to, company):
    graph = [[] for _ in range(city_nodes)]
    for i in range(len(city_from)):
        graph[city_from[i] - 1].append((1, city_to[i] - 1))
        graph[city_to[i] - 1].append((1, city_from[i] - 1))
    heap = [(0, company - 1)]
    distance = [city_nodes + 1 for _ in range(city_nodes)]
    distance[company - 1] = 0
    city_order = []
    while heap:
        cur = heapq.heappop(heap)
        if cur[1] + 1 != company:
            city_order.append(cur[1] + 1)
        for vertex in graph[cur[1]]:
            if distance[cur[1]] + vertex[0] < distance[vertex[1]]:
                distance[vertex[1]] = distance[cur[1]] + vertex[0]
                heapq.heappush(heap, (distance[vertex[1]], vertex[1]))
    return city_order

. 1point 3 acrescity_nodes = 5. Χ
city_from = [1, 2, 2]
city_to = [2, 3, 4]
company = 1
print('Case in description: ', order(city_nodes, city_from, city_to, company))
city_nodes = 5. 1point3acres.com 
city_from = [1, 1, 2, 3, 1]
city_to = [2, 3, 4, 5, 5]
company = 1
print('Test Case 0: ', order(city_nodes, city_from, city_to, company))
city_nodes = 3. 1point3acres
city_from = [1]
city_to = [2]
company = 2
print('Test Case 1: ', order(city_nodes, city_from, city_to, company))