Напишите программу, которая будет реализовывать поиск в ширину в ориентированном невзвешенном не-мульти графе без петель. Вершины графа являются целыми неотрицательными числами в диапазоне от 0 до N–1 (где N — количество вершин в графе). Граф обязательно представлять списками смежности, а именно — как vector<int>[].
В первой строке задано число NUM — количество различных поисков в ширину, которые нужно выполнить (на разных графах). Далее следуют NUM блоков, каждый из которых имеет следующую структуру.
Первая строка блока содержит два числа N и M, разделенные пробелом — количество вершин и количество ребер графа. Далее следуют M строк, каждая из которых содержит по два числа (разделенные пробелом, от 0 до N–1 каждое) — начало и конец соответствующей дуги. Далее, в последней строке блока, записано единственное число от 0 до N–1 — вершина, начиная с которой нужно запустить поиск.
Количество различных графов в одном тесте NUM не превышает 5, количество вершин N не превышает 60000, количество рёбер M не превышает 125000.
Выведите на стандартный выход (экран) NUM строк, в каждой из которых по Ni чисел, разделенных пробелами — расстояния от указанной начальной вершины орграфа до его 0-й, 1-й, 2-й и т. д. вершин (допускается лишний пробел после последнего числа). Если некоторая вершина недостижима из указанной начальной, вместо расстояния выводите число 987654321.
2 3 2 0 1 1 2 1 4 4 0 1 0 3 1 2 2 3 0
987654321 0 1 0 1 2 1
Напишите программу, которая будет реализовывать поиск в ширину в простом графе, вершины которого не нумерованы и идентифицируются словесными названиями.
В первой строке входных данных задано число NUM — количество различных поисков в ширину, которые нужно выполнить (на разных графах). Далее следуют NUM блоков, каждый из которых имеет следующую структуру.
Первая строка блока содержит целое число M — количество ребер графа. Далее следуют M строк, каждая из которых содержит по два названия — концы соответствующего ребра. Названия гарантированно не содержат пробелов и отделены друг от друга одним пробелом. Далее, в последней строке блока, записано единственное название — вершина, начиная с которой нужно запустить поиск (это название гарантированно хоть раз упоминалась как конец одного из ребер).
Количество различных графов в одном тесте NUM не превышает 5, количество рёбер в графе не превышает 50000.
Выведите на стандартный выход (экран) NUM блоков, в каждом из которых записаны расстояния от указанной начальной вершины до всех достижимых (если есть недостижимые вершины, они вообще не упоминаются). Перечень должен быть отсортирован по названиям вершин, каждая пара (название, расстояние) должна выводиться в отдельной строке, блоки должны быть отделены друг от друга строкой «===» (три знака «равно»).
Задачу можно решить, пользуясь map<string,int> и vector<string> для преобразований имен в номера и номеров в имена; тогда внутри программы можно использовать представление графа как vector<vector<int> >. Для вывода в отсортированном порядке использовать прохождение по всем элементам от begin() до end() структуры map<string,int> (превращающей названия в номера).
Другой способ — вообще отказаться от нумерации вершин числами и представлять граф как map<string,vector<string> >; в этом случае массивы, используемые самим поиском, следует заменить на map<string,int>.
2 2 Cherk Zol Cherk Sm Zol 4 A Bb Bb Ccc Ccc A Dddd Eeeee Bb
Cherk 1 Sm 2 Zol 0 === A 1 Bb 0 Ccc 1
Напишите программу, которая будет находить расстояния в неориентированном взвешенном графе с неотрицательными длинами ребер, от указанной вершины до всех остальных. Программа должна работать быстро для больших разреженных графов.
В первой строке входных данных задано число NUM — количество различных запусков алгоритма Дейкстры (на разных графах). Далее следуют NUM блоков, каждый из которых имеет следующую структуру.
Первая строка блока содержит два числа N и M, разделенные пробелом — количество вершин и количество ребер графа. Далее следуют M строк, каждая из которых содержит по три целых числа, разделенные пробелами. Первые два из них в пределах от 0 до N–1 каждое и обозначают концы соответствующего ребра, третье — в пределах от 0 до 20000 и обозначает длину этого ребра. Далее, в последней строке блока, записанное единственное число от 0 до N–1 — вершина, расстояния от которой надо искать.
Количество различных графов в одном тесте NUM не превышает 5. Количество вершин не превышает 60000, рёбер — 200000.
Выведите на стандартный выход (экран) NUM строк, в каждой из которых по Ni чисел, разделенных пробелами — расстояния от указанной начальной вершины взвешенного неориентированного графа до его 0-й, 1-й, 2-й и т. д. вершин (допускается лишний пробел после последнего числа). Если некоторая вершина недостижима от указанной начальной, вместо расстояния выводите число 2009000999 (гарантировано, что все реальные расстояния меньше).
1 5 7 1 2 5 1 3 2 2 3 4 2 4 3 3 4 6 0 3 20 0 4 10 1
18 0 5 2 8
Группа Pink Floyd собирается отправиться в новый концертный тур по всему миру. По предыдущему опыту группа знает, что солист Роджер Уотерс постоянно нервничает при перелетах. На некоторых маршрутах он теряет вес от волнения, а на других — много ест и набирает вес.
Известно, что чем больше весит Роджер, тем лучше выступает группа, поэтому требуется спланировать перелеты так, чтобы вес Роджера на каждом концерте был максимально возможным.
Группа должна посещать города в том же порядке, в котором она дает концерты. При этом между концертами группа может посещать промежуточные города.
Первая строка входного файла содержит три натуральных числа \(n\), \(m\) и \(k\) — количество городов в мире, количество рейсов и количество концертов, которые должна дать группа соответственно (\(n \le 100\), \(m \le 10\,000\), \(2 \le k \le 10\,000\)). Города пронумерованы числами от \(1\) до \(n\).
Следующие \(m\) строк содержат описание рейсов, по одному на строке. Рейс номер \(i\) описывается тремя числами \(b_i\), \(e_i\) и \(w_i\) — номер начального и конечного города рейса и предполагаемое изменение веса Роджера в миллиграммах (\(1 \le b_i, e_i \le n\), \(-100\,000 \le w_i \le 100\,000\)).
Последняя строка содержит числа \(a_1, a_2, ..., a_k\) — номера городов, в которых проводятся концерты (\(a_i \neq a_{i+1}\)). В начале концертного тура группа находится в городе \(a_1\).
Гарантируется, что группа может дать все концерты.
Первая строка выходного файла должна содержать число \(l\) — количество рейсов, которые должна сделать группа. Вторая строка должна содержать \(l\) чисел — номера используемых рейсов.
Если существует такая последовательность маршрутов между концертами,
что Роджер будет набирать вес неограниченно, то первая строка выходного
файла должна содержать строку „infinitely kind“.
4 8 5 1 2 -2 2 3 3 3 4 -5 4 1 3 1 3 2 3 1 -2 3 2 -3 2 4 -10 1 3 1 2 4
6 5 6 5 7 2 3
4 8 5 1 2 -2 2 3 3 3 4 -5 4 1 3 1 3 2 3 1 -2 3 2 -3 2 4 10 1 3 1 2 4
infinitely kind
Переведите каждого из двух коней из одной клетки в другую за наименьшее общее число ходов. Два коня не могут одновременно находиться в одной клетке. Ходы коней должны чередоваться.
Во входном файле записаны координаты первого и второго коня, затем координаты клеток, куда нужно их переместить.
Программа должна вывести последовательность ходов коней в виде нескольких строк. Первым символом в строке должен быть номер коня (1 или 2), затем, через пробел, координаты клетки, в которую он переставляется. Необходимо вывести любое из возможных оптимальных решений. Кони должны ходить по очереди, первым может ходить любой из коней, кони могут сделать различное число ходов.
a1 c2 c2 a1
1 b3 2 a1 1 d4 2 b3 1 c2 2 a1