Задача: Автомобилист хочет проехать от города 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
3 3 3 1 3 1 2 2 1 3 4 2 3 2 0
3 3 3 1 3 1 2 2 1 3 4 2 3 1 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
Я использую поиск в ширину с дополнительными условиями, алгоритм достаточно прост. Но моё решение выдаёт ошибки на некоторых тестах (входные данные на которых происходит ошибка я не знаю). Подскажите, пожалуйста, что не так в алгоритме. Либо посоветуйте иной способ решения.
Отслеживать
9,789 3 3 золотых знака 29 29 серебряных знаков 42 42 бронзовых знака
задан 25 окт 2019 в 11:05
KABAN PUNK KABAN PUNK
1,118 1 1 золотой знак 6 6 серебряных знаков 20 20 бронзовых знаков
Не могу понять: если есть два пути, один 100 км и 3 заправки (бака хватает на 40 км, между городами по 25 км, заправлять надо на 25, 50, 75 км), второй 120 км и 2 заправки (бака хватает на 40 км, между городами по 40, заправлять надо на 40 и 80 км), то какой выбираем? По расстоянию надо выбирать первый, по заправкам второй.
Разбор 9 задания | ОГЭ по информатике 2021
25 окт 2019 в 20:29
выбирать всегда по наименьшему количеству заправок
26 окт 2019 в 8:56
на каком ресурсе можно потестировать решение?
28 окт 2019 в 12:29
регистрация там закрытая, так что свободно тестировать, к сожалению, не получится
28 окт 2019 в 13:22
Time Limit, ML сколько?
30 окт 2019 в 7:15
2 ответа 2
Сортировка: Сброс на вариант по умолчанию
Задача на самом деле достаточно простая. Давайте посмотрим на ограничения. 10к вершин. 500км запаса хода максимум (!!). Кстати можно сразу убирать дороги длиннее k, всё равно проехать не сможем.
А теперь самый интересный момент — из 1 вершины сделаем k вершин которые будут показывать количество заправок на маршруте от старта к i , при этом в пункте i осталось d км топлива.
Оценим сложность. 10к * 500 = 5кк. По памяти это около 20 мегабайт. По времени. 5кк вершин. Количество ребёр в сумме пусть тоже будет 5кк.
Алгоритм комбинированного обхода (или как его правильно) O( (N+M) ) ~ 10kk вполне успевает. Идея алгоритма — идём без заправок пока можем, но складываем отдельно места где можно заправится. Потом эти места обрабатываем в порядке очереди.
Ну как бы и всё. Дальше дело техники сделать переход. Из i->j переход возможен только из вершин где топлива достаточно (обычный цикл от длины до k) без увеличения ответа. И с увелечением ответа на 1 в k — длину.
Ответ — минимум по всем «размноженным» последним вершинам.
Реализацию проще делать через хранение массива [0,k] в каждой обычной вершине.
Код пока не пишу. Если возникнут вопросы по реализации — помогу.
Отслеживать
ответ дан 30 окт 2019 в 10:57
9,789 3 3 золотых знака 29 29 серебряных знаков 42 42 бронзовых знака
ideone.com/hYkXHN примерное решение на С++. Ввод сами раскоментируете)
30 окт 2019 в 11:56
Алгоритм Дейскстры тут не нужен, поскольку тут всё дуги имеют веса 0 или 1 — подойдёт комбинированый обход в глубину-ширину (это так же, как обход в ширину, но с декой вместо очереди).
30 окт 2019 в 12:04
30 окт 2019 в 12:04
Обход в глубину-ширину проще, поскольку каждая вершина обходится всего 1 раз. Нет всяких там операций min. Плюс требуется намного меньше памяти под очереди.
30 окт 2019 в 12:09
30 окт 2019 в 12:11
Предлагаю решение, похожее на алгоритм Дейкстры. Не уверен, можно ли в принципе уложиться во временной лимит 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 = for k in range(1, roads_num + 1)> while roads_num > 0: city_a, city_b, distance = map(int, input().split()) if distance 0: cities_with_gs = 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 = fuel_left_dict = 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
Тестирование
cnt = 1 while True: try: print(find_shortest_path(), end=») print(f»t#Case № «) 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
Источник: ru.stackoverflow.com
Не дорога программа дорог алгоритм перефразировать
⌨️На данной странице, вы можете сделать рерайт текста онлайн, причем совершенно бесплатно. Мы разработали программу, использующую алгоритм нейросетей, которая позволяет в течении нескольких секунд сделать умный, автоматический рерайтинг текста в режиме реального времени, при этом абсолютно бесплатно. В базе нашей программы для рерайта миллионы слов и словосочетаний. Приложение постоянно дорабатывается и совершенствуется.
Конечно, автоматический рерайт текста не может быть идеальным и никогда не заменит человеческого мышления, однако он может заметно сэкономить для вас время, нерв и деньги. На какой процент поднимается уникальность после автоматического рерайта, зависит от стартового процента оригинальности вашего документа, от тематики текста и системы проверки. Рекомендуем, после обработки файла, пройтись по тексту и исправить недочеты (окончания, неправильно вставленные местами слова и прочее.) Если вы хотите купить данную программу, оформить заказ можно на данной странице.
Если вы хотите заказать ручной, авторский рерайт, сделайте бесплатный расчет стоимости вашего заказа. Мы сделаем расчет стоимости и сроков выполнения работы. Студентам, рекомендуем воспользоваться услугой “Кодировка текста”, которая позволит поднять документ до любого процента в течении 1 минуты в автоматическом режиме и пройти Антиплагиат ВУЗ без знака “подозрительный документ”. Для расчета стоимости “Кодировки” документа нажмите кнопку в левом верхнем углу сайта.
Источник: killer-antiplagiat.ru
Русские Блоги
Кратчайший путь, тема 1 | CodeForces 601A-гибридный алгоритм Дейкстры
Кратчайший путь, тема 1 | CodeForces 601A-гибридный алгоритм Дейкстры
Предисловие
Этот одиннадцатый не пошел играть, потратил некоторое время на написание упомянутого выше редактора уценки, эта статья написана этим редактором 2333, сегодня мы собираемся написать нашу новую тему -Кратчайший путь. Кроме того, темы упомянутой ранее темы в основном используют серию kuangbin. Теперь я передумал. Все темы используют темы на CodeForces. Основная причина заключается в том, что внутренние системы OJ, такие как POJ, не могут читать исходный код, а качество тем немного невысокое, и тогда нет никаких различий. степень.
CodeForces может видеть сильно написанный от руки код, качество вопросов относительно лучше, а затем сложность каждого вопроса отмечена буквами / b / c / d.
Хорошо, начните изучать вопрос.
601A. The Two Routes
In Absurdistan, there are n towns (numbered 1 through n) and m bidirectional railways. There is also an absurdly simple road network — for each pair of different towns x and y, there is a bidirectional road between towns x and y if and only if there is no railway between them. Travelling to a different town using one railway or one road always takes exactly one hour.
Есть n городов и m железнодорожных путей с двусторонним движением. Существует также дорожная сеть. Для каждой пары городов x и y, если в них нет железных дорог, должны быть дороги. Чтобы попасть в другой город, по железной дороге или по дороге нужно час.
A train and a bus leave town 1 at the same time. They both have the same destination, town n, and don’t make any stops on the way (but they can wait in town n). The train can move only along railways and the bus can move only along roads.
Поезд и автобус отправляются от станции 1 одновременно и идут до n одновременно.
You’ve been asked to plan out routes for the vehicles; each route can use any road/railway multiple times. One of the most important aspects to consider is safety — in order to avoid accidents at railway crossings, the train and the bus must not arrive at the same town (except town n) simultaneously.
Вам необходимо спланировать свой план путешествия. Каждый маршрут может быть автомобильным или железнодорожным. Во избежание несчастных случаев поезда и автомобили не могут прибывать в один и тот же город одновременно (кроме n).
Under these constraints, what is the minimum number of hours needed for both vehicles to reach town n (the maximum of arrival times of the bus and the train)? Note, that bus and train are not required to arrive to the town n at the same moment of time, but are allowed to do so.
Input
The first line of the input contains two integers n and m (2 ≤ n ≤ 400, 0 ≤ m ≤ n(n — 1) / 2) — the number of towns and the number of railways respectively.
Первая строка содержит два целых числа n и m, где n — количество городов, а m — количество железных дорог.
Each of the next m lines contains two integers u and v, denoting a railway between towns u and v (1 ≤ u, v ≤ n, u ≠ v).
Строка m ниже представляет маршрут
You may assume that there is at most one railway connecting any two towns.
Output
Output one integer — the smallest possible time of the later vehicle’s arrival in town n. If it’s impossible for at least one of the vehicles to reach town n, output — 1.
Вывести кратчайший путь
Examples
input
4 2
1 3
3 4
Note
In the first sample, the train can take the route 1 → 3 → 4 1to3to4 1 → 3 → 4 and the bus can take the route 1 → 2 → 4 1to2to4 1 → 2 → 4 . Note that they can arrive at town 4 at the same time.
In the second sample, Absurdistan is ruled by railwaymen. There are no roads, so there’s no way for the bus to reach town 4.
Для простейшей задачи о кратчайшем пути вес можно считать равным 1.
Основная идея состоит в том, что есть две дороги, железная дорога и шоссе, и два вида транспорта не могут встретиться на полпути.
Кроме того, там, где есть железные дороги, определенно нет дорог.
В этом случае будет вывод, который По крайней мере, один вид трафика может быть напрямую от 1 до n. 。
Таким образом, вам нужно только проложить кратчайший путь для другого.
#include #include #include // Рисунок int g[410][410]; // Длина пути от узла 0 до узла i int d[410]; int main() #ifdef __MSYS__ freopen(«test.txt», «r», stdin); #endif // вводная часть int n, m; scanf(«%d%d», m); for (int i = 0; i m; i++) int a, b; scanf(«%d%d», b); —a, —b; g[a][b] = g[b][a] = 1; > std::queueint> q; // Помещаем в узел 0 q.push(0); memset(d, -1, sizeof(d)); d[0] = 0; while (!q.empty()) int v = q.front(); q.pop(); // последний узел if (v == n — 1) printf(«%dn», d[v]); return 0; > // Обходим все соседние узлы for (int i = 0; i n; i++) // g [v] [i] равно 0, g [0] [n-1] равно 1, если поезд подключен напрямую, то g [v] [i] не может иметь поезд, то есть 0, расчет — это вагон Кратчайший путь // g [v] [i] равно 1, g [0] [n-1] равно 0, если поезд не подключен напрямую, то вагон должен быть подключен напрямую, и вычисляется кратчайший путь поезда if (g[v][i] ^ g[0][n — 1]) if (d[i] == -1) q.push(i); d[i] = d[v] + 1; > > > printf(«-1n»); return 0; >
Используется здесь Dijkstra (Обратите внимание, что здесь нет буквы l) Алгоритм, здесь мы кратко рассмотрим алгоритм dij.
Сначала для сети G выберем точкуAВ качестве отправной точки поставьте в очередь Q.
Затем мы начинаем обрабатывать очередь Q, и если в Q есть элементы, продолжаем выполнение.
Каждый раз, когда он выполняется, элемент v с наименьшим значением d получается из очереди, а затем проходит соседний узел i этого v. Если d [i] является INF, то есть расстояние от узла A бесконечно, то этот элемент Добавить в Q, обновить d [i] = min .
Для алгоритма dij граф можно разделить на две части: одна — это граф кратчайшего пути G1 для dij, а остальная часть — это граф G2, который не был добавлен. Каждый цикл будет искать узел i в G2, этот узел i должен быть наименьшим значением d в G2, а затем обновлять значение d узла, смежного с узлом i. Весь процесс состоит в том, что узлы G2 переходят в G1, и, наконец, G1 является графом кратчайшего пути.
Персональный публичный номер (acm-clan):Алгоритм ACM ежедневно
Сосредоточьтесь на исследовании основных алгоритмов, углубленном анализе вопросов алгоритма ACM, пять минут чтения, легкость понимания каждой строчки исходного кода. Контент включает алгоритмы, C / C ++, машинное обучение и т. Д.
Источник: russianblogs.com