Условие:
Не секрет, что некоторые программисты очень любят путешествовать. Хорошо всем известный программист Петя тоже очень любит путешествовать, посещать музеи и осматривать достопримечательности других городов.
Для перемещений между из города в город он предпочитает использовать машину. При этом он заправляется только на станциях в городах, но не на станциях по пути. Поэтому он очень аккуратно выбирает маршруты, чтобы машина не заглохла в дороге. А ещё Петя очень важный член команды, поэтому он не может себе позволить путешествовать слишком долго. Он решил написать программу, которая поможет ему с выбором очередного путешествия. Но так как сейчас у него слишком много других задач, он попросил вас помочь ему.
Расстояние между двумя городами считается как сумма модулей разности по каждой из координат. Дороги есть между всеми парами городов.
Формат ввода
В первой строке входных данных записано количество городов
n(2≤n≤1000). В следующих n строках даны два целых числа: координаты каждого города, не превосходящие по модулю миллиарда. Все города пронумерованы числами от 1 до n в порядке записи во входных данных.
В следующей строке записано целое положительное число k, не превосходящее двух миллиардов, — максимальное расстояние между городами, которое Петя может преодолеть без дозаправки машины.
В последней строке записаны два различных числа — номер города, откуда едет Петя, и номер города, куда он едет.
Формат вывода
Если существуют пути, удовлетворяющие описанным выше условиям, то выведите минимальное количество дорог, которое нужно проехать, чтобы попасть из начальной точки маршрута в конечную. Если пути не существует, выведите -1.
Я полтора месяца изучаю программирование и знания пока что не очень глубокие. Думал как написать код на основе подсказки (что расстояние - это сумма модулей разности между координатами). Сделал так, чтобы полученные данные правильно были записаны и думал, как вычислить разность между каждой парой городов, но пока не догадался до конца как правильно это сделать.
Написал то, что думал:
#Вводим количество городов
num_cit = int(input())
geo_dict = {}
#Записываем координаты каждого города в словарь
for i in range(1, num_cit + 1):
coord = input()
loc_x_y = coord.split(' ')
geo_dict[i] = loc_x_y
#Преобразовываем координаты в целые числа
for key, value in geo_dict.items():
n = 0
for i in value:
value[n] = int(i)
n += 1
#Макимальное расстояние, которое он может преодолеть без дозаправки
max_distant = input()
#Города, откуда и куда (списком)
way = input()
way = way.split(' ')
n = 0
for i in way:
way[n] = int(i)
n += 1
#Логика (расстояние между городами)
n = 2
for i in range(1, num_cit + 1):
x, y = geo_dict[i][0], geo_dict[i][1]
i = []
for loc in geo_dict.values():
if n <= num_cit:
next_x, next_y = geo_dict[n][0], geo_dict[n][1]
cur = abs(x - next_x) + abs(y - next_y)
i.append(cur)
n += 1
P.S. прочитал, что требуется построение графов, но с таким пока что не сталкивался, может посоветуете, что почитать для лучшего понимания подобных задач:)
Задание странное, как я понял надо достичь города не по кратчайшему пути (мин. расстояние), а посетив как можно меньше городов Хотя если расстояние считаются просто по прямой, то видимо это кратчайшее и есть + в городе обычно медленнее ехать )
Наверно тут надо что-то типа алгоритма Дейкстры. Между узлами нет ребра если не хватит топлива, расстояние между всеми подходящими считать одинаковым (1).
Хотя если расстояние считаются просто по прямой, то видимо это кратчайшее и есть + в городе обычно медленнее ехать )