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