e-olymp 34. Слово спонсора

Задача

По завершению турнира «Новогодняя ночь» спонсор решил отправить $m$ призерам подарки по почте. Зная количество участников $n$ и время доставки почты между некоторыми отделениями «Укрпочты», найти, через какое минимальное время последний из призеров получит свой приз.

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

Первая строка содержит $3$ числа: количество участников турнира $n$, количество призов спонсора $m$ и количество известных временных сроков доставки между некоторыми из отделений $k$. В следующей строке через пробел указаны номера участников, ставших призёрами.

Далее идет $k$ строк по $3$ числа в каждой с информацией об известных сроках доставки между некоторыми из отделений в формате: $a$ $b$ $t$, где $a$ и $b$ — номера отделений, $t$ $(0 \leqslant t \leqslant 365)$ — время доставки почты между ними. В последней строке находится единственное число — номер почтового отделения, из которого спонсор будет отправлять призы. Известно, что $1 \leqslant n, m, a, b \leqslant 365$.

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

Если все призы будут доставлены участникам — вывести в первой строке «The good sponsor!», а в следующей — время, через какое последний из призеров получит свой приз. Если хотя бы один из участников не сможет получить приз — вывести в единственной строке «It is not fault of sponsor…». Фразы выводить без кавычек.

Тесты

Входные данные Выходные данные
1. 3 2 2
2 3
1 2 3
2 3 4
1
The good sponsor!
7
2. 5 1 4
5
1 3 2
2 3 3
4 2 5
4 5 6
1
The good sponsor!
16
3. 7 2 6
1 3
1 3 2
2 4 32
4 5 94
3 1 0
6 2 4
7 2 3
7
It is not fault of sponsor…
4. 5 2 6
1 2
3 1 1
3 4 2
2 4 3
5 1 4
4 5 5
2 3 7
2
The good sponsor!
6

Код программы

Первый вариант

Второй вариант

 

Объяснение

В данной задаче нам нужно построить граф, где будет $n$ вершин (по количеству участников) и $k$ рёбер (по количеству путей). Граф будет взвешенный и неориентированный. Также у нас будет список $m$ вершин (наши победители) и нам нужно проверить, достижимы ли они из начальной вершины (её номер указывается отдельно в самом конце).

К первому варианту кода

Итак, по входным данным мы строим список смежности и после запускаем поиск в ширину (BFS) из стартовой вершины. Так как граф взвешенный, расстоянием до вершины будем считать совокупный вес рёбер на пути к ней от стартовой вершины. Находясь в какой-либо вершине, мы проверяем, куда мы можем попасть из неё. Если сопряжённая вершина не посещена, то мы добавляем её в план. А если она уже посещена, мы проверяем, будет ли путь через вершину в которой мы находимся, короче того пути, которым мы добирались до этой сопряжённой вершины ранее. Если это так, то мы просто заменяем значение в счётчике пути для сопряжённой вершины и добавляем её в план, ведь если путь до неё стал короче, то и путь «через» неё тоже. После того, как мы нашли наикратчайшие пути до всех достижимых вершин, мы проверяем достигли ли мы всех из списка победителей и находим расстояние до самого дальнего из них. И вывод в зависимости от результата.

Ко второму варианту кода

По входным мы строим матрицу смежности. Для несуществующих рёбер мы ставим значение бесконечность ($10^6$ нам подходит, так как это то значение, которое нам не достичь по ограничениям), а для остальных — их вес. А дальше, из стартовой вершины мы запускаем алгоритм Дейкстры, находя кратчайшие пути до каждой вершины. После идёт проверка, всех ли необходимых вершин мы достигли и расстояние до самой дальней из них. И вывод, в зависимости от результата.

Ссылки

E-olymp (условие).

Ideone (первый вариант кода).

Ideone (второй вариант кода).

Related Images:

e-olimp 122. Горные маршруты

Задача. Горный туристический комплекс состоит из n турбаз, соединенных между собой k горными переходами (другие маршруты в горах опасны). Любой переход между двумя базами занимает 1 день. Туристическая группа находится на базе a и собирается попасть на базу b не более чем за d дней. Сколько существует разных таких маршрутов (без циклов) между a и b?
Ссылка на задачу

Пояснение к решению

Поиск путей представляет из себя модифицированный обход в глубину. Вместо массива «глобально посещённых» вершин, в которые уже нельзя возвращаться при обходе, я использую массив «локально посещённых» вершин. Это позволяет использовать одну и ту же вершину в разных, в том числе очень длинных и извращённых путях (в стандартном варианте ищется кратчайший путь, а нам нужны все: в том числе длинные и извращённые).

Кроме того, добавлен параметр depth — длина рассматриваемого в данный момент пути (или глубина текущего рекуррентного вызова, если угодно). Этот параметр изначально имеет значение 0 и при каждом вызове сравнивается с максимально допустимым значением. Перед рекуррентным вызовом мы увеличиваем значение depth, ведь длина нового пути будет на 1 больше. После вызова, т.е. возвращаясь на предыдущий уровень рекурсии, мы уменьшаем длину пути (ведь мы «отбросили» последнюю вершину, т.е. длина пути уменьшилась на 1).

Алгоритм работает примерно так: сначала посещаем начальную вершину и помечаем её как локально посещённую. Если она — искомая, увеличиваем количество найденных путей на 1 и алгоритм завершает свою работу (путей без циклов, содержащих более одной вершины, в этом случае быть не может). Если же начальная вершина не совпадает с целевой, то для всех вершин, в которые можно попасть из неё, применяем рекуррентно тот же алгоритм. Если таких вершин нет, алгоритм завершается, возвращая 0 (нет ни одного пути из начальной вершины в конечную). Если же такие вершины имеются, то увеличиваем параметр «глубина» и вызываем для них рекуррентно наш алгоритм. После выхода из рекурсии, возвращаем параметр «глубина» к последнему его значению (тем, что было перед вызовом) и, чтобы мы могли использовать данную вершину в других путях помечаем её как «локально свободную».

Стоит отметить, что в общем случае задача поиска всех простых путей (пусть даже удовлетворяющих определённым условиям, как в данной задаче) является NP-полной, т.е. решается исключительно переборными алгоритами, работающими за неполиномиальное время (более эффективных алгоритмов для решения таких задач на сегодняшний день неизвестно; кто их найдёт, получит миллион долларов; я не нашёл). Также отметим, что простая модификация приведённого алгоритма позволяет не только вычислять количество простых путей указанной длины, но и перечислять их.

Решение на С++

Решение на Java

 

Related Images: