Все языки Python 3.7.3
Ограничение времени 0.2 секунды 0.8 секунд Ограничение памяти 10Mb 30Mb Ввод стандартный ввод или input.txt Вывод стандартный вывод или output.txt
Дан невзвешенный неориентированный граф. В графе может быть несколько кратчайших путей между какими-то вершинами. Найдите количество различных кратчайших путей между заданными вершинами. Требуемая сложность O(V+E). Формат ввода
v: кол-во вершин (макс. 50000), n: кол-во ребер(макс. 200000), n пар реберных вершин, пара вершин (u, w) для запроса. Формат вывода
Количество кратчайших путей от v к w.
Ограничение времени 1 секунда Ограничение памяти 20Mb Ввод стандартный ввод или input.txt Вывод стандартный вывод или output.txt
Требуется отыскать самый короткий маршрут между городами. Из города может выходить дорога, которая возвращается в этот же город.
Требуемое время работы O((N + M)log N), где N – количество городов, M – известных дорог между ними. N ≤ 10000, M ≤ 250000. Длина каждой дороги ≤ 10000. Формат ввода
Первая строка содержит число N – количество городов.
Вторая строка содержит число M - количество дорог.
Каждая следующая строка содержит описание дороги (откуда, куда, время в пути). Все указанные дороги двусторонние. Между любыми двумя городами может быть больше одной дороги.
Последняя строка содержит маршрут (откуда и куда нужно доехать). Формат вывода
Вывести длину самого короткого маршрута.