| Условие задачи | | Прогресс |
|
Темы:
Обход в ширину
Витя хочет придумать новую игру с числами. В этой игре от игроков требуется преобразовывать четырехзначные числа не содержащие нулей при помощи следующего разрешенного набора действий:
1. Можно увеличить первую цифру числа на 1, если она не равна 9.
2. Можно уменьшить последнюю цифру на 1, если она не равна 1.
3. Можно циклически сдвинуть все цифры на одну вправо.
4. Можно циклически сдвинуть все цифры на одну влево.
Например, применяя эти правила к числу 1234 можно получить числа 2234, 1233, 4123 и 2341 соответственно. Точные правила игры Витя пока не придумал, но пока его интересует вопрос, как получить из одного числа другое за минимальное количество операций.
Входные данные: на вход подаются два различных четырехзначных числа, каждое из которых не содержит нулей. Каждое число с новой строки
Выходные данные: Программа должна вывести последовательность четырехзначных чисел, не содержащих нулей. Последовательность должна начинаться первым из данных чисел и заканчиваться вторым из данных чисел, каждое последующее число в последовательности должно быть получено из предыдущего числа применением одного из правил. Количество чисел в последовательности должно быть минимально возможным.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
1234
4321 |
1234
2234
3234
4323
4322
4321 |
| |
![]()
|
|
Темы:
Обход в ширину
Очередь
В неориентированном графе требуется найти длину кратчайшего пути между двумя вершинами.
Формат входных данных
В первой строке входных данных записано число N - количество вершин в графе (1 <= N <= 100). Далее с новой строки записана матрица смежности (0 обозначает отсутствие ребра, 1 - наличие ребра). В последней строке записаны номера двух вершин - начальной и конечной.
Формат входных данных
Выведите длину кратчайшего пути. Если пути не существует, выведите одно число -1.
| |
![]()
|
ID 22020.
Путь
Темы:
Обход в ширину
В неориентированном графе требуется найти минимальный путь между двумя вершинами.
Формат входных данных
В первой строке записано число N - количество вершин в графе (1 <= N <= 100). В следующих строках задана матрица смежности (0 обозначает отсутствие ребра, 1 - наличие ребра). В последней строке записаны номера двух вершин - начальной и конечной.
Формат выходных данных
Выведите сначала L - длину пути (количество ребер, которые нужно пройти). Затем выведите L+1 число - вершины в порядке следования вдоль этого пути. Если пути не существует, выведите одно число -1.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
3 5
|
3
3 2 1 5 |
| |
![]()
|
|
Темы:
Обход в ширину
На шахматной доске NxN в клетке (x1, y1) стоит голодный шахматный конь. Он хочет попасть в клетку (x2, y2), где растет вкусная шахматная трава. Какое наименьшее количество ходов он должен для этого сделать?
Формат входных данных
На вход программы поступает пять чисел: N, x1, y1, x2, y2 (\(5 <= N <= 20\), \(1 <= x_1,\ y_1,\ x_2,\ y_2 <= N\)). Левая верхняя клетка доски имеет координаты (1, 1), правая нижняя - (N, N).
Формат входных данных
Выведите единственное число K - наименьшее необходимое число ходов коня.
| |
![]()
|
|
Темы:
Обход в ширину
Одна из Сверхсекретных организаций, чье название мы не имеем право разглашать, представляет собой сеть из N подземных бункеров, соединенных равными по длине туннелями, по которым из любого бункера можно добраться до любого другого (не обязательно напрямую). Связь с внешним миром осуществляется через специальные засекреченные выходы, которые расположены в некоторых из бункеров.
Организации понадобилось составить план эвакуации персонала на случай экстренной ситуации. Для этого для каждого из бункеров необходимо узнать, сколько времени потребуется для того, чтобы добраться до ближайшего из выходов. Вам, как специалисту по таким задачам, поручено рассчитать необходимое время для каждого из бункеров по заданному описанию помещения Сверхсекретной организации. Для вашего же удобства бункеры занумерованы числами от 1 до N.
Формат входных данных
В первых двух строках вводятся два натуральных числа N, K (\(1 <= N <= 100000\), \(1 <= K <= N\)) — количество бункеров и количество выходов соответственно. В третьей строке через пробел записаны K различных чисел от 1 до N, обозначающих номера бункеров, в которых расположены выходы. В четвертой строке идёт число M (\(1 <= M <= 100000\)) — количество туннелей. В следующих M строках вводятся пары чисел – номера бункеров, соединенных туннелем.
По каждому из туннелей можно двигаться в обе стороны. В организации не существует туннелей, ведущих из бункера в самого себя, зато может существовать более одного туннеля между парой бункеров.
Формат выходных данных
Выведите N чисел, разделенных пробелом — для каждого из бункеров минимальное время, необходимое чтобы добраться до выхода. Считайте, что время перемещения по одному туннелю равно 1.
| |
![]()
|
|
Темы:
Обход в ширину
Разбор случаев
В стране из предыдущей задачи много специалистов не только по защите детей, но и про проектированию городов. Поэтому, чтобы решить проблему пробок в перенаселенной столице раз и навсегда, было решено построить новую столицу и перенести все правительство туда. Сказано — сделано.
Улицы в новой столице образуют правильную прямоугольную сетку, в которой все улицы пересекаются ровно через одну местную единицу длины. Вертикально идущие улицы называются улицами, а горизонтально идущие — аллеями. Всего в городе получилось 2000 улиц и 2000 аллей, поэтому, чтобы не придумывать много новых названий, их все просто пронумеровали. Улицы пронумеровали с запада на восток числами от −1000 до 999, а аллеи — с юга на север, тоже числами от −1000 до 999. Центром города считаются кварталы на пересечении улиц и аллей с номерами от −100 до 100.
Чтобы увеличить пропускную способность дорог в городе, было решено сделать все улицы и аллеи односторонними. По улицам с четными номерами разрешается ехать только с севера на юг, а по улицам с нечетными номерами — только с юга на север. Аналогично, по аллеям с четными номерами можно ехать только с востока на запад, а с нечетными — только с запада на восток.
Сколько местных единиц длины придется проезжать мэру новой столицы каждый вечер, возвращаясь из мэрии города домой? И мэрия, и дом мэра находятся в центре города. Мэр едет домой кратчайшим путем, соблюдая, впрочем, правила дорожного движения.
Входные данные
В первой строке даны два числа x1 и y1 — номер улицы и номер аллеи, на пересечении которых находится мэрия. В второй строке даны два числа x2 и y2 — номер улицы и номер аллеи, на пересечении которых находится дом мэра. Все числа целые и не превосходят по модулю 100.
Выходные данные
Выведите одно число: длину кратчайшего пути от мэрии до дома мэра на автомобиле.-
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
0 0
1 1 |
4 |
| 2 |
3 5
2 4 |
4 |
| |
![]()
|
|
Темы:
Обход в ширину
Двумерные массивы
Вы являетесь одним из разработчиков новой компьютерной игры. Игра происходит на прямоугольной доске, состоящей из W×H клеток. Каждая клетка может либо содержать, либо не содержать фишку (см. рисунок).
Важной частью игры является проверка того, соединены ли две фишки путем, удовлетворяющим следующим свойствам:
1. Путь должен состоять из отрезков вертикальных и горизонтальных прямых.
2. Путь не должен пересекать других фишек.
При этом часть пути может оказаться вне доски. Например:
Фишки с координатами (1, 3) и (4, 4) могут быть соединены. Фишки с координатами (2, 3) и (5, 3) тоже могут быть соединены. А вот фишки с координатами (2, 3) и (3, 4) соединить нельзя — любой соединяющий их путь пересекает другие фишки.
Вам необходимо написать программу, проверяющую, можно ли соединить две фишки путем, обладающим вышеуказанными свойствами, и, в случае положительного ответа, определяющую минимальную длину такого пути (считается, что путь имеет изломы, начало и конец только в центрах клеток (или “мнимых клеток”, расположенных вне доски), а отрезок, соединяющий центры двух соседних клеток, имеет длину 1).
Формат входных данных
Первая строка входного файла содержит два натуральных числа: W — ширина доски, H — высота доски (1 ≤ W, H ≤ 75). Следующие H строк содержат описание доски: каждая строка состоит ровно из W символов: символ “X” (заглавная английская буква “экс”) обозначает фишку, символ “.” (точка) обозначает пустое место. Все остальные строки содержат описания запросов: каждый запрос состоит из четырех натуральных чисел, разделенных пробелами — X1, Y1, X2, Y2, причем 1 ≤ X1, X2 ≤ W, 1 ≤ Y1, Y2 ≤ H. Здесь (X1, Y1) и (X2, Y2) — координаты фишек, которые требуется соединить (левая верхняя клетка имеет координаты (1, 1)). Гарантируется, что эти координаты не будут совпадать (кроме последнего запроса). Последняя строка содержит запрос, состоящий из четырех чисел 0; этот запрос обрабатывать не надо. Количество запросов не превосходит 20.
Формат выходных данных
Для каждого запроса необходимо вывести одно целое число на отдельной строке — длину кратчайшего пути, или 0, если такого пути не существует.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5 4
XXXXX
X...X
XXX.X
.XXX.
2 3 5 3
1 3 4 4
2 3 3 4
0 0 0 0
|
5
6
0 |
| 2 |
4 4
XXXX
.X..
..X.
X...
1 1 3 1
0 0 0 0
|
4 |
| |
![]()
|
|
Темы:
Обход в ширину
Задачи на моделирование
В подземелье есть N залов, соединенных туннелями. В некоторых залах находятся роботы, которые одновременно получили команду собраться в одном месте.
Роботы устроены так, что, получив команду, они все начали двигаться с такой скоростью, что туннель между двумя любыми залами преодолевают за 1 минуту. Роботы не могут останавливаться (в том числе и в залах), а также менять направление движения, находясь в туннелях (однако попав в зал, робот может из него пойти по тому же туннелю, по которому он пришел в этот зал).
Напишите программу, вычисляющую, через какое минимальное время все роботы смогут собраться вместе (в зале или в туннеле).
Входные данные
Сначала на вход программы поступают числа N — количество залов (1≤N≤400) и K — количество туннелей (1≤K≤20000). Далее вводится K пар чисел, каждая пара описывает номера залов, соединяемых туннелем (по туннелю можно перемещаться в обе стороны). Между двумя залами может быть несколько туннелей. Туннель может соединять зал с самим собой. Далее следует число M (1≤M≤400) — количество роботов. Затем вводятся M чисел, задающих номера залов, где вначале расположены роботы. В одном зале может быть несколько роботов.
Выходные данные
Выведите минимальное время в минутах, через которое роботы могут собраться вместе. Если роботы никогда не смогут собраться вместе, выведите одно число –1 (минус один).
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4 5
1 2
2 3
3 4
1 4
1 3
3
1 2 4 |
1 |
| 2 |
3 2
1 2
2 3
2
1 3 |
1 |
| |
![]()
|
|
Темы:
Алгоритмы на графах
Кратчайшие пути в графе
Обход в ширину
Вам дано дерево с N вершинами. Здесь дерево - это разновидность графа, а точнее, связный неориентированный граф с N−1 ребром, где N - количество его вершин. I-е ребро (\(1<=i<=N-1\)) соединяет вершины ai и bi и имеет длину ci.
Вам также дано Q запросов и целое число K. Для каждого j-го запроса (\(1<=j<=Q\)) найдите длину кратчайшего пути от вершины xj к вершине yj через вершину K.
Входные данные
В первой строке записано целое число N (\(3<=N<=10^5\)). В следующих N строках записаны вершины ai и bi (\(1<=a_i,b_i<=N\), \(1<=i<=N-1\)) и длина между ними ci (\(1<=c_i<=10^9\), \(1<=i<=N-1\))
Далее идут два числа Q и K (\(1<=Q<=10^5\), \(1<=K<=N\)). В последних Q строках записаны целые числа xj, yj (\(x_j \neq y_j\),\(x_j \neq K\), \(y_j \neq K\) \(1<=j<=Q\), ).
Заданный граф является деревом.
Выходные данные
Выведите ответы на запросы в Q строках. В j-й строке выведите ответ на j-й запрос.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
5
1 2 1
1 3 1
2 4 1
3 5 1
3 1
2 4
2 3
4 5 |
3
2
4 |
Кратчайшие пути для трех запросов следующие:
Запрос 1: Вершина 2 → Вершина 1 → Вершина 2 → Вершина 4: Длина 1 + 1 + 1 = 3
Запрос 2: Вершина 2 → Вершина 1 → Вершина 3: Длина 1 + 1 = 2
Запрос 3: Вершина 4 → Вершина 2 → Вершина 1 → Вершина 3 → Вершина 5: Длина 1 + 1 + 1 + 1 = 4 |
| 2 |
7
1 2 1
1 3 3
1 4 5
1 5 7
1 6 9
1 7 11
3 2
1 3
4 5
6 7 |
5
14
22 |
Путь для каждого запроса должен проходить через вершину K = 2. |
| 3 |
10
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
7 8 1000000000
8 9 1000000000
9 10 1000000000
1 1
9 10 |
17000000000 |
|
| |
![]()
|
|
Темы:
Обход в ширину
Дана таблица, состоящая из N строк и M столбцов. В каждой клетке таблицы записано одно из чисел: 0 или 1. Расстоянием между клетками (x1, y1) и (x2, y2) назовем сумму |x1-x2|+|y1-y2|. Вам необходимо построить таблицу, в клетке (i, j) которой будет записано минимальное расстояние между клеткой (i, j) начальной таблицы и клеткой, в которой записана 1. Гарантируется, что хотя бы одна 1 в таблице есть.
Формат входных данных
В первой строке вводятся два натуральных числа N и M, не превосходящих 500. Далее идут N строк по M чисел - элементы таблицы.
Формат выходных данных
Требуется вывести N строк по M чисел - элементы искомой таблицы.
| |
![]()
|
|
Темы:
Обход в ширину
На стандартной шахматной доске (8х8) живут 2 шахматных коня: Красный и Зеленый. Обычно они беззаботно скачут по просторам доски, пощипывая шахматную травку, но сегодня особенный день: у Зеленого коня День Рождения. Зеленый конь решил отпраздновать это событие вместе с Красным. Но для осуществления этого прекрасного плана им нужно оказаться на одной клетке. Заметим, что Красный и Зеленый шахматные кони сильно отличаются от черного с белым: они ходят не по очереди, а одновременно, и если оказываются на одной клетке, никто никого не съедает. Сколько ходов им потребуется, чтобы насладиться праздником?
Входные данные
На вход программы поступают координаты коней, записанные по стандартным шахматным правилам (т.е. двумя символами - маленькая латинская буква (от a до h) и цифра (от 1 до 8), задающие столбец и строку соответственно).
Выходные данные
Требуется вывести наименьшее необходимое количество ходов, либо число -1, если кони не могут встретиться.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
a1 a3 |
1 |
| |
![]()
|
Темы:
Обход в ширину
Некоторые деревни соединены между собой дорогами, которые можно представить в виде неориентированного графа. Вершины данного графа - это деревни, а ребра - дороги между деревнями (граф может содержать циклы). Известно, что в деревне S основана артель коробейников. Каждое утро, чтобы продать свою мелкую галантерею, коробейники выходят в деревни, которые еще не посетили, и в которые есть дорога из текущей. Артель коробейников всегда делится на группы так, чтобы они могли за один день обойти все деревни, которые имеют дороги из текущей.
За сколько дней коробейники посетят все деревни?
Напишите функцию \(bfs()\), которая будет возвращать ответ на задачу.
Входные данные
В первой строке вводятся 3 целых числа n, m, s ( \(1 <= n <= 10^5\), \(0 <= m <= 10^5\), \(1 <= s <= n\)) - количество деревень, количество дорог между ними и номер деревни, в которой основана артель коробейников. В следующих m строках содержится по 2 числа u, v( \(1 <= u, v <= n\)) - номера двух деревень, между которыми есть дорога. Индексация деревень ведется с 1.
Выходные данные
Выведите одно число - за сколько дней коробейники посетят все деревни.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
6 7 1
1 2
1 5
2 3
5 4
3 4
3 6
4 6 |
4 |
| |
![]()
|
|
Темы:
Обход в ширину
Обход в глубину
Из прямоугольного листа клетчатой бумаги (M строк, N столбцов) удалили некоторые клетки. На сколько кусков распадётся оставшаяся часть листа? Две клетки не распадаются, если они имеют общую сторону.
Входные данные
В первой строке находятся числа M и N, в следующих M строках - по N символов. Если клетка не была вырезана, этому соответствует знак #, если вырезана - точка. 1 <= M, N <= 100.
Выходные данные
Вывести одно число.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5 10
##..#####.
.#.#.#....
###..##.#.
..##.....#
.###.#####
|
5
|
| |
![]()
|
|
Темы:
Обход в ширину
Беззработный Дэйв от скуки соорудил в собственной гостиной лабиринт из картонных коробок. Лабиринт содержит K входов. Когда его подружка Энни вернулась, лабиринт невероятным образом разросся изнутри, а сам горе-изобретатель там заблудился и не может выбраться.
Единственное, что нашла Энни в комнате это карту лабиринта, который имеет размеры NхM клеток. На карте было обозначено место, в котором находится Дэйв (как так вышло никто не знает). Клетки лабиринта либо пустые, по которым можно пройти, либо в них находится стена и по ним проходить нельзя. У клетки может быть до 4-х смежных клеток, в которую можно пройти из текущей.
Энни пригласила вас помочь ей определить, с какого входа нужно начать свой путь, чтобы побыстрее дойти до Дейва. Если таких входов несколько, Энни пойдет со входа с наименьшим номером.
Входные данные
Программа получает на вход несколько строк. В первой строке - 2 числа N и M (1<= N, M <= 100, NxM <= 100), размеры лабиринта. Далее следует N строк по M символов в каждой - описание лабиринта. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с Дэйвом.
В (N+2)-й строке находится число K (1<=K<=NxM) -- количество входов в лабиринт. Далее в K строках содержатся координаты входов. В i-й строке содержатся числа xi и yi, означающие,что i-й вход расположен в xi-й строке и в yi-м столбце (1<=xi<=N,1<=yi<=M).
Координаты входов попарно различны, все входы расположены в пустых клетках. Ни один из входов не находится в клетке с Дэйвом.
Выходные данные
Выведите одно число - номер входа (нумерация начинается с 1). Если до Дэйва невозможно добраться, выведите -1.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5 5
00000
00000
10*00
01111
00000
4
1 1
1 5
4 1
5 5
|
1
|
| 2 |
3 3
010
1*1
010
4
1 1
1 3
3 1
3 3
|
-1
|
| |
![]()
|
|
Темы:
Обход в ширину
Аборигены с планеты Шешинера очень любят земные ананасы. Побывав у них в гостях, Алиса решила отправить несколько штук им в подарок. На то, чтобы доставить ананасы свежими есть всего 24 часа.
Алиса хочет хочет отправить как можно большее число ананасов. Капитан Полосков решил ей помочь и с радостью согласился слетать на своем космическом корабле. Но есть один нюанс: на некоторых космических маршрутах можно дозаправить корабль, не превышающий максимально установленный вес. А заправлять корабль в пути нужно всегда, иначе он просто не долетит. Поэтому если корабль заполнить ананасами по максимуму, то, его не получится дозаправить в пути и поэтому не удастся воспользоваться самым коротким маршрутов, и придётся лететь через другие планеты. Может случиться даже так, что корабль не успеет долететь до Шешинеры вовремя, и ананасы испортятся.
Итак, сколько же ананасов можно погрузить в космический корабль, чтобы доставить груз вовремя?
Входные данные
Программа получает на вход несколько строк. В первой строке находятся числа n (1 <= n <= 500) и m - количество планет и количество космических маршрутов между планетми, соответственно. В следующих m строках записана информация о маршрутах. Каждый маршрут описывается в отдельной строке следующим образом. Сначала указаны номера планет, которые соединяются космическим маршрутом, потом время, которое тратится на перелет по этому маршруту, и, наконец, максимальный космического корабля, который можно заправить на этом маршруте. Известно, что все космические маршруты соединяют различные планеты, причем для каждой пары планет есть не более одного маршрута, непосредственно их соединяющий. Все числа разделены одним или несколькими пробелами.
Планеты нумеруются числами от 1 до n. Планеты Земля имеет номер 1, а планета Шешинера - номер n. Время перелета по маршруту задано в минутах и не превосходит 1440 (24 часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что один ананас весит 100 грамм, а пустой корабль - 3 тонны.
Выходные данные
Выведите одно число - максимальное количество ананасов, которое можно доставить, потратив не более 24часов.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3 3
1 2 10 3000220
2 3 20 3000201
1 3 1 3000099
|
2
|
| |
![]()
|
|
Темы:
Алгоритм Флойда
Обход в ширину
Кладоискателю Васе попалась карта древнего подземелья. Подземелье представляет собой лабиринт размера N×M (1 ≤ N, M ≤ 100 , N×M ≤ 100). Каждая клетка лабиринта либо пуста и по ней можно пройти, либо содержит стену. Из клетки можно переходить только в смежную по стене клетку (так, у каждой клетки может быть не более 4 смежных).
В одной из клеток находится клад, который и хочет достать Вася. В лабиринте есть K входов, из которых Вася может начать свой путь.
Требуется определить, с какого входа Васе нужно начать свой путь, чтобы пройденное расстояние до клада было наименьшим. Если таких входов несколько, нужно вывести вход с наименьшим номером.
Входные данные
Первая строка содержит 2 числа N и M, задающие размеры лабиринта. Далее следует описание лабиринта: N строк по M символов в каждой. 0 означает, что клетка свободна; 1, что в клетке находится стена. Символ * обозначает клетку с сокровищем (такая клетка в лабиринте ровно одна).
В (N+2)-й строке находится число K (1 ≤ K ≤ NxM) -- количество входов в лабиринт. Далее в K строках содержатся координаты входов. Так, в i-й строке содержатся числа xi и yi, означающие,что i-й вход расположен в xi-й строке и в yi-м столбце (1 ≤ xi ≤ N, 1 ≤ yi ≤ M). Гарантируется, что координаты входов попарно различны, и то, что все входы расположены в пустых клетках. Ни один из входов не находится в клетке с сокровищем.
Выходные данные
Необходимо вывести одно число - искомый номер входа (нумерация начинается с 1). Если до сокровища невозможно добраться, выведите -1.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5 5
00000
00000
10*00
01111
00000
4
1 1
1 5
4 1
5 5
|
1 |
| 2 |
3 3
010
1*1
010
4
1 1
1 3
3 1
3 3
|
-1 |
| |
![]()
|
|
Темы:
Обход в ширину
Структуры данных
Алгоритмы на графах
В научно-исследовательском институте чародейства и волшебства пожар! Во время опыта Кор- неева В. П. по превращению всей морской и океанской воды планеты в живую воду произошло короткое замыкание, и теперь его кабинет объят пламенем. Задача первостепенной важности — спасти из огня ценные лабораторные приборы, в особенности единственный в своём роде диван- транслятор µ-поля. Ваша задача — перенести диван-транслятор из кабинета Корнеева в запасную лабораторию изучения µ-поля.
НИИЧАВО состоит из N кабинетов, соединённых M коридорами. Кабинеты пронумерованы це- лыми числами от 1 до N, при этом кабинет Корнеева имеет номер A, а лаборатория изучения µ-поля расположена в кабинете номер B. Благодаря специальному искажению пространства внутри инсти- тута, все коридоры имеют одинаковую длину, которую можно пройти за 1 минуту, если двигаться быстрым шагом.
Ситуация усугубляется тем, что диван-транслятор — прибор, очень чувствительный к резким пе- репадам температуры. Внутри каждого коридора НИИЧАВО поддерживается свой температурный режим. Если абсолютная величина разности температур в двух последовательных коридорах на пути из кабинета Корнеева в лабораторию окажется больше D градусов, то диван-транслятор пе- рейдёт в нестабильное состояние, что может привести к катастрофическим последствиям. Обратите внимание, что на своём пути вы не заходите в сами кабинеты, а только переходите из коридора в коридор, поэтому климат внутри кабинетов не влияет на диван-транслятор. В силу причин магиче- ского характера, войдя в коридор, вы обязаны дойти до его конца, иными словами, останавливаться или разворачиваться посреди коридора запрещено. По каждому коридору можно перемещаться в обоих направлениях.
Определите, за какое минимальное время можно добраться из кабинета Корнеева до запасной лаборатории, не допуская резкого перепада температур. В рамках данной задачи вам предлагается ответить на поставленный вопрос для нескольких пар значений A и B.
Формат входных данных
В первой строке входных данных следуют три целых числа N, M и D (2 <= N <= 100 000, 1 <= M <= 200 000, 0 <= D <= 2 · 108 ), обозначающие количество кабинетов, количество коридоров в НИИЧАВО и максимальный допустимый перепад температур для дивана-транслятора в граду- сах. В последующих M строках находятся описания коридоров. Каждая строка содержит по три целых числа ui , vi , ti — номера двух кабинетов, соединённых i-м коридором, и значение температуры в этом коридоре, выраженное в градусах (1 <= ui , vi <= N, −109 <= ti <= 109 ). Как вы уже могли понять, НИИЧАВО — весьма необычное заведение, поэтому между двумя кабинетами может пролегать несколько коридоров, возможно с разными температурами, а некоторые коридоры могут соединять кабинет с самим собой. Гарантируется, что коридоры перечислены во входном файле в порядке неубывания ti . В следующей строке находится целое число Q (1 <= Q <= 50) — количество пар A и B, которые вам требуется обработать. В каждой из последующих Q строк находятся по два целых числа Ai , Bi , обозначающих номер кабинета Корнеева и номер кабинета, в котором расположена лаборатория (1 <= Ai , Bi <= N, Ai != Bi).
Формат выходных данных
Для каждого набора данных выведите в отдельной строке минимальное количество минут, ко- торое требуется потратить, чтобы добраться из кабинета Корнеева до лаборатории, либо выведите −1, если сделать это, используя допустимый для дивана-транслятора маршрут, невозможно.
Примеры
| Ввод |
Вывод |
6 9 5
6 6 -42
1 2 4
2 3 6
3 2 7
2 5 11
6 1 12
1 3 15
3 4 16
5 6 18
2
1 5
4 2 |
4
-1 |
6 9 7
6 6 -42
1 2 4
2 3 6
3 2 7
2 5 11
6 1 12
1 3 15
3 4 16
5 6 18
1
4 2 |
5 |
Замечание
Пояснение к тестам из условия. В обоих тестах план НИИЧАВО выглядит следующим образом:
Рассмотрим первый тест, в нём D = 5. В первом наборе A = 1, B = 5. В качестве воз- можного маршрута может выступить следующая последовательность переходов по коридорам:
 Третьим шагом можно вернуться в кабинет 2 и по тому же коридору с t = 6 .
Во втором наборе A = 4, B = 2. Способа добраться из кабинета 4 в кабинет 2, ни разу не допустив перепад температуры больше, чем в 5 градусов, не существует.
Во втором тесте D = 7. В единственном наборе A = 4, B = 2 cтартовый и конечный кабинет те же, что и во втором наборе первого теста из условия, но допустимый перепад температур больше, благодаря чему подходит следующий маршрут: 
| |
![]()
|
|
Темы:
Кратчайшие пути в графе
Обход в ширину
Способы задания графа
Миша путешествует по стране на автомобиле. В стране есть несколько городов, соединенных дорогами, на каждой дороге может быть некоторое число ям.
Мише очень нравится ездить по дорогам на которых много ям, - он участвует в популярном телешоу "Неперсистентные машинки" и за каждую посещенную яму ему платят по одной монете.
Он начинает путь в любом из городов страны и затем путешествует по дорогам между городами. По каждой дороге Миша может проехать сколько угодно раз но ему платят за посещение любой ямы только один раз.
Помогите Мише найти самый выгодный маршрут.
Формат входных данных
В первой строке содержатся два целых числа n и m количество городов и дорог соединяющих города в стране соответственно (1 <= n <= 105 , 0<= m <= 105)
В следующих m строках содержится по три целых числа, разделенных пробелами номера, - городов, соединенных очередной дорогой и количество ям на этой дороге соответственно. Количество ям на каждой дороге неотрицательное число не превосходящее 106.
Гарантируется, что никакая дорога не соединяет город с самим собой и что нет двух дорог соединяющих одинаковые пары городов. Вершины нумеруются с единицы.
Формат выходных данных
Выведите одно число максимальное количество монет которое Миша сможет получить.
| Ввод |
Вывод |
4 4
1 2 1
2 3 1
1 4 1
4 3 0 |
3 |
4 2
1 3 5
2 4 4 |
5 |
Замечание
Все дороги двусторонние; проехав в любую сторону по дороге, Миша посещает все ямы на этой дороге. Обратите внимание, что между некоторыми парами городов может не существовать пути по имеющимся дорогам.
| |
![]()
|
|
Темы:
Обход в ширину
Магистр Максимус отправился в опасное путешествие в горы Ордена Магов. Внутри гор великими магами прошлого созданы комнаты, в каждой из которых хранятся магические артефакты. Максимус желает пройти через все n комнат, но, как оказалось, все комнаты заперты, за исключением комнаты 0, в которую Максимус уже вошел.
В каждой комнате имеется набор уникальных заклинаний, открывающих двери других комнат. Магистр Максимус познал язык великих магов, поэтому он может легко прочитать эти заклинания и отпирать другие комнаты.
Максимус хочет посетить все комнаты и найти все магические артефакты. Однако, для этого ему необходимо найти заклинания открывающие каждую дверь.
По известному набору заклинаний, определите сможет ли Максимум получить все артефакты или нет.
Формат входных данных
В первой строке записано число n (2 <= n <= 1000), количество комнат. Далее идет n строк. В i-й строке описываются заклинания, хранящиеся в этой комнате. В каждой из этих строк первое число (m, 0 <= m <= 1000) обозначает количество уникальных заклинаний, которые открывают комнаты, далее записаны m уникальных чисел rooms[i](0 <= rooms[i][j] < n) - номера комнат, которые открывают эти заклинания (0<=i<n, 1 <= общее количество заклинаний во всех комнатах <= 10000).
Формат выходных данных
Выведите True, если Максимус может посетить все комнаты и найти все магические артефакты, или False в противном случае.
| |
![]()
|
|
Темы:
Обход в ширину
В Сильвертауне есть N районов с номерами от 1 до N и M дорог с номерами от 1 до M. Используя дорогу i, вы можете добраться из района Ai в район Bi или наоборот за один час.
Сколько существует путей, по которым можно добраться из района 1 в район N как можно быстрее?
Поскольку число может быть огромным, выведите его по модулю 109+7
Формат входных данных
Первая строка содержит два целых числа N и M. Далее идет M строк, в каждой из которых записано по 2 числа: Ai и Bi.
Ограничения
2 ≤ N ≤ 2×1050 ≤ M ≤ 2×1051 ≤ Ai < Bi ≤ NПары (Ai,Bi) уникальны.Все значения во входных данных целые числа.
Формат выходных данных
Выведите ответ на задачу.
| |
![]()
|