Профессор Флойд и профессор Дейкстра ненавидят друг друга. После переезда университета во вновь отстроенный университетский городок они потребовали себе кабинеты в зданиях, максимально удалённых друг от друга. Вам поручено найти расстояние между двумя такими зданиями.
Иными словами, требуется найти два здания, кратчайший путь между которыми наибольший среди всех пар зданий, и вывести длину этого пути. Так как профессорам иногда все же нужно встречаться, путь между выбранными зданиями должен существовать.
В первой строке находятся два числа \(N\) и \(M\) - количество зданий и количество дорог, соединяющих здания (\(1 \le N \le 100, 0 \le M \le \frac{N \cdot (N-1)}{2}\)). Далее в \(M\) строках расположены описания дорог: 3 целых числа \(s_i\), \(e_i\), \(l_i\) - здания, в которых начинается и заканчивается дорога и длина дороги соответственно (\(1 \le s_i, e_i \le N, 0 \le l_i \le 100\), дороги двунаправленные).
Необходимо вывести одно число - искомое расстояние.
3 2 1 2 1 2 3 2
3
3 0
0
Сегодня у студентов праздник! В одном из новых зданий университета решили открыть столовую. Для этих целей требуется выбрать одно из зданий, в котором и будет располагаться столовая. Чтобы студенты как можно меньше отвлекались от учёбы, было решено выбрать такое здание, чтобы максимальное расстояние от него до всех остальных зданий было как можно меньше.
Помогите найти такое здание!
В первой строке находятся два числе \(N\) и \(M\) - количество зданий и количество дорог, соединяющих здания (\(1 \le N \le 100, 0 \le M \le \frac{N \cdot (N-1)}{2}\)). Далее в \(M\) строках расположены описания дорог: 3 целых числа \(s_i\), \(e_i\), \(l_i\) - здания, в которых начинается и заканчивается дорога и длина дороги соответственно (\(1 \le s_i, e_i \le N, 0 \le l_i \le 100\), дороги двунаправленные).
Необходимо вывести одно число - номер искомого здания. Если есть несколько зданий удовлетворяющих поставленным критериям, выберите среди них здание с наименьшим номером.
3 2 1 2 1 2 3 2
2
3 1 1 2 10
1
Профессор Флойд живёт в очень опасном районе города. Ежедневно бандиты грабят на улицах прохожих. Читая криминальную хронику, профессор Флойд вычислил вероятность быть ограбленным при проходе по каждой улице города.
Теперь он хочет найти наиболее безопасный путь от дома до университета, в котором он преподаёт. Иными словами, он хочет найти путь от дома до университета, для которого вероятность быть ограбленным минимальна.
В первой строке находятся два числа \(N\) и \(M\) - количество зданий и количество улиц, соединяющих здания (\(1 \le N \le 100, 1 \le M \le \frac{N \cdot (N-1)}{2}\)). В следующей строке находятся числа \(S\) и \(E\) -- номер дома, в котором живёт профессор и номер дома, в котором находится университет соответственно. Далее в \(M\) строках расположены описания дорог: 3 целых числа \(s_i, e_i, p_i\) - здания, в которых начинается и заканчивается дорога и вероятность в процентах быть ограбленным, пройдя по дороге соответственно (\(1 \le s_i, e_i \le N, 0 \le p_i \le 100\), дороги двунаправленные). Гарантируется, что существует хотя бы один путь от дома профессора до университета.
Необходимо вывести одно число - минимальную возможную вероятность быть ограбленным. Выведите ответ с максимально возможной точностью.
3 3 1 3 1 2 20 1 3 50 2 3 20
0.36
На плоскости задано множество точек (x, y), где x, y – целые числа, 1≤x≤M, 1≤y≤N. Из каждой точки выходит ровно один из следующих векторов: (-1,-1), (-1,0), (-1,1), (0,1), (1,1), (1,0), (1,-1), (0,-1). Каждый вектор соединяет одну целочисленную точку плоскости с другой. Например, если из точке (2, 5) выходит вектор (1, 1), то он соединяет эту точку с (3, 6), но не наоборот.
Последовательность из двух и более точек плоскости a1, a2,…, ak назовем циклом, если каждая точка ai соединена вектором с ai+1 (1≤i≤k-1), и ak соединена вектором с a1. Циклы считаются разными если они отличаются хотя бы одной вершиной.
Напишите программу, которая по информации о векторах, выходящих из точек плоскости, находит количество различных циклов.
Первая строка входного файла содержит два целых числа N (1≤N≤100) и M (1≤M≤100). Каждая из последующих N строк, содержит M пар чисел (т.е. 2≤M чисел). Пара x, которая находится в строке y, задает вектор в точке (x, y).
Единственная строка выходного файла должна содержать целое число – количество циклов, образованных векторами.
2 4 -1 1 -1 1 -1 0 0 1 1 0 1 0 0 -1 0 -1
2
Игрушечный лабиринт представляет собой прозрачную плоскую прямоугольную коробку, внутри которой есть препятствия и перемещается шарик. Лабиринт можно наклонять влево, вправо, к себе или от себя, после каждого наклона шарик перемещается в заданном направлении до ближайшего препятствия или до стенки лабиринта, после чего останавливается. Целью игры является загнать шарик в одно из специальных отверстий – выходов. Шарик проваливается в отверстие, если оно встречается на его пути (шарик не обязан останавливаться в отверстии).
Первоначально шарик находится в левом верхнем углу лабиринта. Гарантируется, что решение существует и левый верхний угол не занят препятствием или отверстием.
В первой строке входного файла записаны числа N и M – размеры лабиринта (целые положительные числа, не превышающие 100). Затем идет N строк по M чисел в каждой – описание лабиринта. Число 0 в описании означает свободное место, число 1 – препятствие, число 2 – отверстие.
Выведите единственное число – минимальное количество наклонов, которые необходимо сделать, чтобы шарик покинул лабиринт через одно из отверстий.
4 5 0 0 0 0 1 0 1 1 0 2 0 2 1 0 0 0 0 1 0 0
3