Собственно есть 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