Собственно есть 3 версии данной задачи

http://www.e-olimp.com.ua/problems/1726 (1)

http://www.e-olimp.com.ua/problems/1727 (2)

http://www.e-olimp.com.ua/problems/1728 (3)

Рассмотрим решение (1). Используем дейкстру, но будем искать не минимальное расстояние до вершины v, а минимальную сумму, которую придется потратить в худшем случае, добравшись до вершины v, заплатив 1 раз. Переход будет таким: если мы находимся в вершине from и хотим сделать переход в вершину to, то dp[to] = min(dp[to], max(dp[from], rib[from][to])) Где rib[from][to] ребро между этими двумя вершинами. Это решение заходит.

Задача (2). Сделаем тоже самое, что и  в (1). Сохраним в dp1. dp2[v] будет хранить минимальную сумму, которую придется потратить в худшем случае, добравшись до вершины v, заплатив 2 раза. Переход будет таким: если мы находимся в вершине from и хотим сделать переход в вершину to, то dp2[to] = min(dp2[to], max(dp2[from],  dp1[from] + rib[from][to])) Таким образом, выбираем что хуже, если мы уже в вершине from: если мы уже заплатили 2 раза или если заплатили 1 раз и на текущем ребре заплатим второй. Отдельно надо рассмотреть случай, если до конечной вершины можно добраться ровно за 1 ход. Такое решение не проходит все тесты. Не могу понять в чем проблема. В идее или реализации?

Если бы это было верно, можно было бы обобщить и на (3).

Код: http://pastebin.com/44Xn0fVh

http://www.e-olimp.com.ua/problems/1726 (1)

http://www.e-olimp.com.ua/problems/1727 (2)

http://www.e-olimp.com.ua/problems/1728 (3)

Рассмотрим решение (1). Используем дейкстру, но будем искать не минимальное расстояние до вершины v, а минимальную сумму, которую придется потратить в худшем случае, добравшись до вершины v, заплатив 1 раз. Переход будет таким: если мы находимся в вершине from и хотим сделать переход в вершину to, то dp[to] = min(dp[to], max(dp[from], rib[from][to])) Где rib[from][to] ребро между этими двумя вершинами. Это решение заходит.

Рассмотрим (2). Используем тот же алгоритм. Сделаем тоже самое, что и в (1), запомним это в dp1. Переход будет аналогичным, но с использованием dp1. dp2[v] хранит минимальную сумму, которую придется потратить в худшем случае, добравшись до вершины v, заплатив 2 раза.  dp2[to] = min(dp2[to], max(dp2[from], dp1[from] + rib[from][to])) Т.е. находим что будет хуже, если мы уже заплатили 2 раза, добравшись до вершины from, либо если до этого заплатили 1 раз и теперь платим на ребре из from в to. Такое решение не проходит все тесты. Совсем не понятно почему.

Понятно, что если это верно, то можно обобщить и на (3).

Ошибка в рассуждениях или нужно искать баг в коде?

http://pastebin.com/44Xn0fVh

http://pastebin.com/ifzGbN2P

http://acm.timus.ru/problem.aspx?space=1&num=1827

Данная задача прошла за 1с. Хотя при сложности O(n * 50 * log M) ~ 8,5 * 10^7 казалось бы должно быть быстрее. Медленные ввод/вывод? Или сервер CF балует своей производительностью, и время выполнения вполне адекватно?

http://acm.timus.ru/problem.aspx?space=1&num=1827

Данная задача прошла за 1с. Хотя при сложности O(n * 50 * log M) ~ 8,5 * 10^7 казалось бы должно быть быстрее. Медленные ввод/вывод? Или же тестирующий сервер CF балует своей производительностью и время выполнения вполне адекватно?

Problems of October 01, 2011 Contest

Team standings of today's contest

Personal standings of today's contest

нужно вычислить a^b mod c. a, b, c до 10^18 2^63-1(если это вдруг принципиально). Как избежать переполнения или без длинки никак?

прошу помощи по задаче:

http://informatics.mccme.ru/moodle/mod/statements/view3.php?id=1974&chapterid=2789#1