Обозначим пункты Бишкек-B; Суусамырская Развилка-A; Жалал-Абад-J; Талас-T; Ош-O; Каракол-K; Балыкчы-L; Нарын-N; БАткен-E.
Растояния между ними (по хорошим дарогам, в километрах) следуюшие;
AT=102; AJ=377; AB=193; JO=106; OE=240; LB=179; LK=216; LN=180
Скорость Машины - 60км/час.
Полное время перелета Ош-Бишкек или Бишкек-Ош --2 часа
По заданным двум пунктам найти минимальное время передвижение между ними (в минутах).
Ввод: две различные заглавные латинкие буквы (обазначение пунктов)
Вывод: одно натуральное число (время в минутах)
Пример: Ввод: L O Вывод:299
дам 70 баллов
Answers & Comments
Ответ:
Для решения этой задачи мы можем построить граф, где вершины будут представлять пункты назначения, а ребра будут представлять собой расстояния между этими пунктами. После этого, мы можем использовать алгоритм Дейкстры для нахождения кратчайшего пути между двумя выбранными вершинами.
Вот Python-код, который решает эту задачу:
Объяснение:
import heapq
def dijkstra(graph, start, end):
heap = [(0, start)]
visited = set()
while heap:
(cost, current) = heapq.heappop(heap)
if current in visited:
continue
visited.add(current)
if current == end:
return cost
for neighbor, weight in graph[current].items():
heapq.heappush(heap, (cost + weight, neighbor))
return float('inf')
# Расстояния между пунктами
distances = {
'A': {'T': 102, 'J': 377, 'B': 193},
'J': {'A': 377, 'O': 106},
'B': {'A': 193, 'O': 240, 'L': 179},
'O': {'B': 240, 'J': 106, 'E': 216},
'K': {'L': 216},
'L': {'B': 179, 'K': 216, 'N': 180},
'N': {'L': 180},
'E': {'O': 216}
}
# Скорость машины в км/ч
speed = 60
# Полное время перелета между Ош и Бишкеком (в часах)
total_time_hours = 2
# Переводим время из часов в минуты
total_time_minutes = total_time_hours * 60
# Запрашиваем ввод пользователя
start_point = input("Введите начальный пункт (латин