4

Задача:

Автомобилист хочет проехать от города 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])

Я использую поиск в ширину с дополнительными условиями, алгоритм достаточно прост. Но моё решение выдаёт ошибки на некоторых тестах (входные данные на которых происходит ошибка я не знаю).

Подскажите, пожалуйста, что не так в алгоритме. Либо посоветуйте иной способ решения.

6
  • Не могу понять: если есть два пути, один 100 км и 3 заправки (бака хватает на 40 км, между городами по 25 км, заправлять надо на 25, 50, 75 км), второй 120 км и 2 заправки (бака хватает на 40 км, между городами по 40, заправлять надо на 40 и 80 км), то какой выбираем? По расстоянию надо выбирать первый, по заправкам второй.
    – MiniMax
    Commented 25 окт. 2019 в 20:29
  • 1
    выбирать всегда по наименьшему количеству заправок
    – KABAN PUNK
    Commented 26 окт. 2019 в 8:56
  • 1
    на каком ресурсе можно потестировать решение?
    – slippyk
    Commented 28 окт. 2019 в 12:29
  • регистрация там закрытая, так что свободно тестировать, к сожалению, не получится
    – KABAN PUNK
    Commented 28 окт. 2019 в 13:22
  • 1
    Time Limit, ML сколько? Commented 30 окт. 2019 в 7:15

2 ответа 2

5
+50

Задача на самом деле достаточно простая. Давайте посмотрим на ограничения. 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] в каждой обычной вершине.

Код пока не пишу. Если возникнут вопросы по реализации - помогу.

5
  • 2
    ideone.com/hYkXHN примерное решение на С++. Ввод сами раскоментируете)
    – pavel
    Commented 30 окт. 2019 в 11:56
  • Алгоритм Дейскстры тут не нужен, поскольку тут всё дуги имеют веса 0 или 1 - подойдёт комбинированый обход в глубину-ширину (это так же, как обход в ширину, но с декой вместо очереди). Commented 30 окт. 2019 в 12:04
  • @PavelMayorov да у меня он и реализован) но по факту это та же самая Дейсктра, просто быстро выбираем минимальную вершину. кстати использовать деку вариант. Я как-то на 2 очередях привык это делать.
    – pavel
    Commented 30 окт. 2019 в 12:04
  • Обход в глубину-ширину проще, поскольку каждая вершина обходится всего 1 раз. Нет всяких там операций min. Плюс требуется намного меньше памяти под очереди. Commented 30 окт. 2019 в 12:09
  • @PavelMayorov то оптимизация была... я её убрал, ничего в целом не поменялось. Памяти одинаково будет. сейчас поменяю посмотрим. Ссылка та же.
    – pavel
    Commented 30 окт. 2019 в 12:11
2

Предлагаю решение, похожее на алгоритм Дейкстры. Не уверен, можно ли в принципе уложиться во временной лимит 2 секунды при использовании Python. Я потестировал это решение на больших рандомных графах - 6000 городов, 9000 дорог, результаты от 0.8 до 4 секунд в зависимости от удачности сложения графа.

Я создавал графы для тестирования с помощью модуля networkx, затем переводил их в нужный для задачи формат. Могу добавить сюда код, если нужно.

Алгоритм

  1. Стартуем из текущего города (в начале это один город - первый, на следующих итерациях перебираем все конечные города предыдущего заезда) и едем до всех возможных городов на расстоянии одного бака. Все эти города можно сразу добавлять в ответ - мы уже знаем количество заправок необходимое, чтобы доехать них.
  2. Проезжая очередной город фиксируем его расстояние до ближайшей заправки в словарь:
    • если город имеет заправку, то расстояние до заправки = 0.
    • если не имеет, то пишем расстояние до ближайшего города с заправкой, из уже посещённых.
  3. Города, дальше которых машина не смогла проехать из-за нехватки топлива, запоминаем - на следующем витке алгоритма будем их заправлять в ближайшем посещённом городе (просто вычитая расстояние до этого города из стартового запаса хода) и повторять шаги 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

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.