#python #алгоритм #графы
Задача:
Автомобилист хочет проехать от города u до города v, по стране с количеством городов
n. Известны длины дорог между всеми городами, дороги двухсторонние. Автомобиль имеет
ограниченный запас топлива k, в начале пути бак полностью заполнен. Восполнять запас
топлива до максимального k он может в некоторых городах по дороге. Нужно посчитать
сколько минимум нужно будет сделать заправок по дороге чтобы попасть из города u в город v.
Формат входных данных
Первая строка содержит пять целых чисел: k — сколько километров может проехать машина
без дозаправок, n — количество городов, m — количество дорог, u — номер города начала
дороги, и v — номер города, куда нужно доехать (1 ≤ k ≤ 500, 2 ≤ n ≤ 10 000, 0 ≤ m
≤ 10 000, 1 ≤ u,v, ≤ n, u ≠ v).
В следующих m строках задаются дороги. В i-й из этих строк записаны три числа p_i,
q_i, r_i —
номера двух городов, которые соединяет очередная двухсторонняя дорога, и её длина.
(1 ≤ p_i, q_i ≤ n, 1≤ r_i ≤ 10^9)
Следующая строка содержит целое число l — количество заправок (0 ≤ l ≤ n). Наконец,
последняя строка содержит l чисел a_1, a_2, . . . , a_i — номера городов с заправками
в порядке возрастания (1 ≤ a_1 < a_2 < ... < a_l ≤ n).
Формат выходных данных
Выведите -1, если невозможно доехать от города с номером u до города с
номером v, или минимальное количество заправок, если это возможно.
Примеры:
input #1:
3 3 3 1 3
1 2 3
1 3 4
2 3 3
2
2 3
output #1:
1
input #2:
3 3 3 1 3
1 2 2
1 3 4
2 3 2
0
output #2:
-1
input #3:
3 3 3 1 3
1 2 2
1 3 4
2 3 1
0
output #3:
0
Ограничение по времени: 2 секунды;
Ограничение по памяти: 512 мегабайт
Моё решение:
k,n,m,u,v = [int(i) for i in input().split()]
adj = {}
for j in range(m):
p,q,r = [int(i) for i in input().split()]
if p-1 in adj:
adj[p-1].append([q-1,r])
else:
adj[p-1] = [[q-1,r]]
if q-1 in adj:
adj[q-1].append([p-1,r])
else:
adj[q-1] = [[p-1,r]]
l = int(input())
refills = [False] * n
if not l is 0:
for i in input().split():
refills[int(i)-1] = True
count = [0] * n
tank = [None] * n
level = [-1] * n
def bfs(s):
global level,charging,k
level[s] = 0
queue = [s]
tank[s] = k
while queue:
v = queue.pop(0)
for w_ in adj[v]:
w = w_[0]; r = w_[1];
if tank[w] is None:
tank[w] = k
if level[w] is -1 and r<=tank[v]:
level[w] = r+level[v]
if refills[w]:
tank[w] = k
count[w]+=1
else:
tank[w] -=r
queue.append(w)
bfs(u-1)
if level[v-1] is -1:
print(-1)
else:
print(count[v-1])
Я использую поиск в ширину с дополнительными условиями, алгоритм достаточно прост.
Но моё решение выдаёт ошибки на некоторых тестах (входные данные на которых происходит
ошибка я не знаю).
Подскажите, пожалуйста, что не так в алгоритме. Либо посоветуйте иной способ решения.
Ответы
Ответ 1
Задача на самом деле достаточно простая. Давайте посмотрим на ограничения. 10к вершин. 500км запаса хода максимум (!!). Кстати можно сразу убирать дороги длиннее k, всё равно проехать не сможем. А теперь самый интересный момент - из 1 вершины {i} сделаем k вершин {(i,d)} которые будут показывать количество заправок на маршруте от старта к i, при этом в пункте i осталось d км топлива. Оценим сложность. 10к * 500 = 5кк. По памяти это около 20 мегабайт. По времени. 5кк вершин. Количество ребёр в сумме пусть тоже будет 5кк. Алгоритм комбинированного обхода (или как его правильно) O( (N+M) ) ~ 10kk вполне успевает. Идея алгоритма - идём без заправок пока можем, но складываем отдельно места где можно заправится. Потом эти места обрабатываем в порядке очереди. Ну как бы и всё. Дальше дело техники сделать переход. Из i->j переход возможен только из вершин где топлива достаточно (обычный цикл от длины до k) без увеличения ответа. И с увелечением ответа на 1 в k - длину. Ответ - минимум по всем "размноженным" последним вершинам. Реализацию проще делать через хранение массива [0,k] в каждой обычной вершине. Код пока не пишу. Если возникнут вопросы по реализации - помогу.Ответ 2
Предлагаю решение, похожее на алгоритм Дейкстры. Не уверен, можно ли в принципе уложиться во временной лимит 2 секунды при использовании Python. Я потестировал это решение на больших рандомных графах - 6000 городов, 9000 дорог, результаты от 0.8 до 4 секунд в зависимости от удачности сложения графа. Я создавал графы для тестирования с помощью модуля networkx, затем переводил их в нужный для задачи формат. Могу добавить сюда код, если нужно. Алгоритм Стартуем из текущего города (в начале это один город - первый, на следующих итерациях перебираем все конечные города предыдущего заезда) и едем до всех возможных городов на расстоянии одного бака. Все эти города можно сразу добавлять в ответ - мы уже знаем количество заправок необходимое, чтобы доехать них. Проезжая очередной город фиксируем его расстояние до ближайшей заправки в словарь: если город имеет заправку, то расстояние до заправки = 0. если не имеет, то пишем расстояние до ближайшего города с заправкой, из уже посещённых. Города, дальше которых машина не смогла проехать из-за нехватки топлива, запоминаем - на следующем витке алгоритма будем их заправлять в ближайшем посещённом городе (просто вычитая расстояние до этого города из стартового запаса хода) и повторять шаги 1, 2, 3. Другими словами: первая заправка - едем во все стороны, добавляя каждый посещённый город в ответ. Топливо кончилось - встали в конечном городе. Пошла вторая заправка. Все вставшие машины заправляем и опять едем до упора. Так мы доберёмся до каждого города на карте. Или недоберёмся - заправки кончились, искомый город не нашли, возвращаем -1. Замечание: все дороги, длина которых больше, чем максимальный запас хода (полный бак) можно исключить в самом начале - на этапе формирования списка смежности. source.py def find_shortest_path(): def make_adj_dict(roads_num, max_pos_dist): adj_dict = {k : {} for k in range(1, roads_num + 1)} while roads_num > 0: city_a, city_b, distance = map(int, input().split()) if distance <= max_pos_dist: adj_dict[city_a][city_b] = distance adj_dict[city_b][city_a] = distance roads_num -= 1 return adj_dict max_possible_distance, cities_num, roads_num, start_city, end_city = map(int, input().split()) adj_dict = make_adj_dict(roads_num, max_possible_distance) refuel_num = int(input()) if refuel_num > 0: cities_with_gs = {int(num) : True for num in input().split()} else: cities_with_gs = {} answers = {} one_tank_reachable_cities = set() one_tank_reachable_cities.add(start_city) should_be_refueled_set = set() dist_to_last_gs = {k : 0 if k in cities_with_gs else float("inf") for k in range(1, cities_num + 1)} fuel_left_dict = {k : 0 for k in range(1, cities_num + 1)} fuel_left_dict[start_city] = max_possible_distance for refuel_cnt in range(refuel_num + 1): if should_be_refueled_set: for city in should_be_refueled_set: fuel_residue = max_possible_distance - dist_to_last_gs[city] if fuel_residue >= 0: fuel_left_dict[city] = fuel_residue one_tank_reachable_cities.add(city) should_be_refueled_set = set() while one_tank_reachable_cities: city_a = one_tank_reachable_cities.pop() answers[city_a] = refuel_cnt for city_b, a_to_b_dist in adj_dict[city_a].items(): dist_to_last_gs[city_b] = min(dist_to_last_gs[city_a] + a_to_b_dist, dist_to_last_gs[city_b]) if city_b in answers: continue fuel_before_ride = fuel_left_dict[city_a] if a_to_b_dist <= fuel_before_ride: one_tank_reachable_cities.add(city_b) fuel_after_ride = fuel_before_ride - a_to_b_dist fuel_left_dict[city_b] = max(fuel_after_ride, fuel_left_dict[city_b]) else: should_be_refueled_set.add(city_a) return answers[end_city] if end_city in answers else -1 Тестирование cnt = 1 while True: try: print(find_shortest_path(), end='') print(f"\t#Case № {cnt}") except EOFError: break cnt += 1 input.txt ### Case № 1, output = 1 3 3 3 1 3 1 2 3 1 3 4 2 3 3 2 2 3 ### Case № 2, output = 0 3 3 3 1 3 1 2 2 1 3 4 2 3 1 0 ### Case № 3, output = -1 3 3 3 1 3 1 2 2 1 3 4 2 3 2 0 ### Case № 4, output = 3 50 7 8 1 7 1 2 50 1 3 50 1 4 50 2 5 50 3 5 60 4 5 40 5 6 40 6 7 30 4 2 3 5 6 ### Case № 5, output = 1 120 7 8 1 7 1 2 50 1 3 50 1 4 50 2 5 50 3 5 60 4 5 40 5 6 40 6 7 30 2 2 3 Строки начинающиеся с ### нужны для наглядности, перед запуском программы их надо убрать. Я их не удаляю из файла input.txt вручную, а пропускаю через sed перед подачей на ввод программы (пользуюсь Ubuntu): ./source.py < <(sed '/#/d' input.txt) Output 1 #Case № 1 0 #Case № 2 -1 #Case № 3 3 #Case № 4 1 #Case № 5
Комментариев нет:
Отправить комментарий