Добрый день!
Есть задача:
Ориентрованный граф с n вершинами задан матрицей смежности.(если a[i][j] == 0 — между i и j ребра нет, a[i][j] > 0 — ребро между i и j есть, и его вес равен a[i][j]).
Также даны два числа v1, v2.
Требуется найти путь с наименьшим весом из вершины v1 в вершину v2, если весом пути считается сумма двух ребер с максимальным весом.
Как ее решить с помощью алгоритма Дейкстры?
А ограничения то какие?
n<=1000 a[i][j] <= 1000000
Перейдем к задаче с одним ребром вместо двух.
Посчитаем для каждой вершины, с каким минимальным возможным весом самого тяжелого ребра мы можем дойти к ней из v1 (можно и Дейкстрой, если хочется). Потом аналогично посчитаем для каждой вершины, с каким минимальным возможным весом самого тяжелого ребра можно дойти из нее в v2 — для этого заменим все ребра на обратные.
Теперь перебираем самое тяжелое ребро в пути и по этим двум предподсчетам смотрим, какой минимальный вес может быть у второго самого тяжелого ребра на пути. Пускай у нас есть ребро из a в b, тогда нужно найти путь из v1 в а и из b в v2, а это у нас уже подсчитано.
Самое тяжелое ребро пути мы как перебираем? просто по всем ребрам идем?
Да, просто делаем предположение давайте посчитаем, что может получиться в таком случае? для всех ребер по очереди.
Здесь еще нужно не затупить и не рассматривать случаи, когда второе самое тяжелое получается тяжелее самого тяжелого, больше вроде ничего особенного.
Все, я понял, спасибо :)
nvm
Можно подробнее?
Куда прикрутить эту функцию и как ее пересчитывать быстро?
Например, для графа
Что и как нужно посчитать для вершины 4, чтобы она знала, что при переходе в пути 1-5 по ребру 4 5 нужно брать 1-2-4, где текущий вес 20 (и итоговый тоже 20), а не 1-3-4, где текущий вес 19 (а итоговый 25).
Challenge Succeeded