Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах
    Кратчайшие пути в графе(116 задач)
    Обход в глубину(100 задач)
    Способы задания графа(54 задач)
    Минимальный каркас(12 задач)
    Потоки(21 задач)
    Паросочетания(17 задач)
    Эйлеров цикл(9 задач)
    Деревья(16 задач)
---> 319 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: 1 2 3 4 5 6 7 >> Отображать по:
#5
Дейкстра
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дан ориентированный взвешенный граф. Найдите кратчайшее расстояние от одной заданной вершины до другой.

Входные данные

В первой строке содержатся три числа: N, S и F (1≤ N≤ 100, 1≤ S, F≤ N), где N – количество вершин графа, S – начальная вершина, а F – конечная. В следующих N строках вводится по N чисел, не превосходящих 100, – матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – присутствие ребра данного веса. На главной диагонали матрицы записаны нули.

Выходные данные

Требуется вывести искомое расстояние или -1, если пути между указанными вершинами не существует.

Примеры
Входные данные
3 2 1
0 1 1
4 0 1
2 1 0
Выходные данные
3
#6
Дейкстра: восстановление пути
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дан ориентированный взвешенный граф. Найдите кратчайший путь от одной заданной вершины до другой.

Входные данные

В первой строке содержатся три числа: N, S и F (1≤N≤100, 1≤S, F≤N), где N – количество вершин графа, S – начальная вершина, а F – конечная. В следующих N строках вводится по N чисел, не превосходящих 100, – матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – присутствие ребра данного веса. На главной диагонали матрицы записаны нули.

Выходные данные

Требуется вывести последовательно все вершины одного (любого) из кратчайших путей, или одно число -1, если пути между указанными вершинами не существует. В ответе примера указано количество вершин, а не сам путь. Ваша программа должна выдавать именно путь.

Примеры
Входные данные
3 2 1
0 1 1
4 0 1
2 1 0
Выходные данные
3
#7
Заправки
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

В стране N городов, некоторые из которых соединены между собой дорогами. Для того, чтобы проехать по одной дороге, требуется один бак бензина. В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в N-ый, потратив как можно меньшее денег. Покупать бензин впрок нельзя.

Входные данные

В первой строке вводится число N (1≤N≤100), в следующей строке идет N чисел, i-ое из которых задает стоимость бензина в i-ом городе (всё это целые числа из диапазона от 0 до 100). Затем идет число M – количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами – номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону), между двумя городами всегда существует не более одной дороги, не существует дорог, ведущих из города в себя.

Выходные данные

Требуется вывести одно число – суммарную стоимость маршрута или -1, если добраться невозможно.

Примеры
Входные данные
5
3 6 1 7 6 
8
1 2
5 4
5 1
3 4
5 2
2 4
2 3
3 1
Выходные данные
3
Входные данные
5
3 7 2 9 4
4
1 2
1 3
2 3
4 5
Выходные данные
-1
#14
Сталкер
  
Темы: [0-1 BFS]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
128 megabytes

В городе Н при невыясненных обстоятельствах территория одного из заводов превратилась в аномальную зону. Все подъезды к территории были перекрыты, а сама она получила название промзоны. В промзоне находятся N зданий, некоторые из них соединены дорогами. По любой дороге можно перемещаться в обоих направлениях.

Начинающий сталкер получил задание добраться до склада в промзоне. Он нашел в электронном архиве несколько карт территории промзоны. Так как карты составлялись разными людьми, то на каждой из них есть информация только о некоторых дорогах промзоны. Одна и та же дорога может присутствовать на нескольких картах.

В пути сталкер может загружать из архива на мобильный телефон по одной карте. При загрузке новой карты предыдущая в памяти телефона не сохраняется. Сталкер может перемещаться лишь по дорогам, отмеченным на карте, загруженной на данный момент. Каждая загрузка карты стоит 1 рубль. Для минимизации расходов сталкеру нужно выбрать такой маршрут, чтобы как можно меньшее число раз загружать карты. Сталкер может загружать одну и ту же карту несколько раз, при этом придется заплатить за каждую загрузку. Изначально в памяти мобильного телефона нет никакой карты.

Требуется написать программу, которая вычисляет минимальную сумму расходов, необходимую сталкеру, чтобы добраться от входа в промзону до склада.

Входные данные

В первой строке входных данных содержатся два натуральных числа N и K (2 ≤ N ≤ 2000; 1 ≤ K ≤ 2000) — количество зданий промзоны и количество карт соответственно. Вход в промзону находится в здании с номером 1, а склад — в здании с номером N.

В последующих строках находится информация об имеющихся картах. Первая строка описания i-ой карты содержит число ri — количество дорог, обозначенных на i-ой карте. Затем идут ri строк, содержащие по два натуральных числа a и b (1 ≤ a, b ≤ N; a ≠ b), означающих наличие на i-ой карте дороги, соединяющей здания a и b. Суммарное количество дорог, обозначенных на всех картах, не превышает 300 000 (r1 + r2 + … + rK ≤ 300 000).

Выходные данные

Выведите одно число — минимальную сумму расходов сталкера. В случае, если до склада добраться невозможно, выведите число –1.

Примеры
Входные данные
12 4
4
1 6
2 4
7 9
10 12
3
1 4
7 11
3 6
3
2 5
4 11
8 9
5
3 10
10 7
7 2
12 3
5 12
Выходные данные
3
#15
Файловый менеджер
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

Петя работает над очень большим проектом. Проект содержит N файлов. В процессе работы Пете часто приходится просматривать и редактировать файлы. Для ускорения работы Петя использует файловый менеджер Fur Manager, который отображает список имен файлов проекта в некотором порядке.

В текущей версии Fur Manager’a для перемещения по списку имен файлов есть следующие возможности:

  1. можно нажать клавишу вниз, при этом курсор перемещается на следующий файл в списке, для последнего файла следующим считается первый;

  2. можно нажать клавишу вверх, при этом курсор перемещается на предыдущий файл в списке, для первого файла предыдущим считается последний;

  3. можно нажать клавишу Alt и, удерживая ее, набрать последовательность латинских букв. После этого клавишу Alt следует отпустить, и в этот момент курсор переместится на ближайший файл, имя которого начинается c заданной последовательности символов. Ближайший файл — это файл, на который можно переместиться за наименьшее количество нажатий клавиши вниз. Если заданная последовательность является началом имени текущего файла, или файла, имя которого начинается с этой последовательности, не существует, то курсор останется на месте.

Первая и вторая из описанных возможностей файлового менеджера требуют по одному нажатию клавиши, а третья — одного нажатия (нажатие клавиши Alt) плюс количество нажатий, равное длине набранной последовательности латинских букв.

Файлы пронумерованы от 1 до N в порядке их следования. После загрузки Fur Manager’а курсор находится на первом файле.

Петя знает, что ему сначала придется редактировать файл с номером a1, затем с номером a2 и так далее, а последним — файл с номером ak. В последовательности a1, a2, ..., ak один и тот же номер может встречаться несколько раз. При каждом перемещении от одного файла к другому Петя хочет нажимать как можно меньше клавиш.

Требуется написать программу, которая выдает искомую последовательность нажатий клавиш.

Входные данные

В первой строке входных данных содержится целое число N (1 ≤ N ≤ 1000) — количество файлов в проекте.

В следующих N строках записаны имена файлов, по одному в каждой строке. Файлы перечислены в том порядке, в котором они отображаются файловым менеджером. Имена состоят только из строчных латинских букв. Длина каждого имени не превосходит 2000 символов. Все имена файлов различны.

Далее в следующей строке записано целое число k (1 ≤ k ≤ 10).

Последняя строка входных данных содержит k целых чисел a1, a2, ..., ak (1 ≤ ai ≤ N) — номера редактируемых файлов. Редактирование файлов выполняется в том порядке, в котором они встречаются в последовательности a1, a2, ..., ak.

Выходные данные

Выведите описание искомой последовательности нажатий клавиш в виде k блоков информации:

  • первый блок информации описывает перемещение от файла с номером 1 к файлу с номером a1;
  • второй блок информации описывает перемещение от файла с номером a1 к файлу с номером a2;
  • …
  • k-ый блок информации описывает перемещение от файла с номером ak–1 к файлу с номером ak.

Каждый блок информации выглядит следующим образом.

В первой строке блока записывается число L — наименьшее количество нажатий клавиш, необходимое для перемещения от очередного файла последовательности к следующему.

Следующие L строк блока описывают нажимаемые клавиши. Каждая из строк содержит описание одной клавиши:

  • если нажимается клавиша вниз, то в строке записывается слово down;
  • если нажимается клавиша вверх, то в строке записывается слово up;
  • если нажимается клавиша Alt, то в строке записывается слово Alt;
  • при нажатии клавиши с латинской буквой выводится соответствующая ей латинская буква.

Если существует несколько оптимальных способов перемещения, то требуется вывести любой из них.

Система оценки
  • Подзадача 1. Решения, верно работающие при \(n \leqslant 30\), оцениваются в 28 баллов. Баллы ставятся при прохождении всех тестов.
  • Подзадача 2. Решения, верно работающие при больших ограничениях, оцениваются по 4 балла за тест..
Примеры
Входные данные
6
a
b
c
d
e
f
4
4 3 1 6
Выходные данные
2
Alt
d
1
up
2
Alt
a
1
up
Страница: 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест