CD
так что ты по-любому K должен в граф писать
Size: a a a
2020 April 30
MB
Кажется, можно возвести матрицу смежности в (K-1)-ую степень
EZ
например, K = 35, путь весом 100 длиной 10 короче пути весом 200 длиной 30, но прибавление пути весом 100 длиной 10 делает его запрещенным
Ок, давай рассмотрим чуть более очевидную модификацию. Продублируем граф К раз
CD
Ок, давай рассмотрим чуть более очевидную модификацию. Продублируем граф К раз
если у тебя вершина (N, K) дейкстра офк работает
EZ
если у тебя вершина (N, K) дейкстра офк работает
Ну
CD
а вот не храня K чисел в ноде нельзя
MB
Кажется, можно возвести матрицу смежности в (K-1)-ую степень
Хотя не уверен, мб лажа.
Но сделать K-1 итерацию флойда точно можно
Но сделать K-1 итерацию флойда точно можно
EZ
а вот не храня K чисел в ноде нельзя
А ну да
CD
Хотя не уверен, мб лажа.
Но сделать K-1 итерацию флойда точно можно
Но сделать K-1 итерацию флойда точно можно
флойда? ФБ?
KK
к слойный бфс
MB
флойда? ФБ?
хм. Видимо такой флойд дествительно вырождается в ФБ
CD
ну вот Михаил вроде верно замечает, что возведение в степень в теме
KK
ну вот Михаил вроде верно замечает, что возведение в степень в теме
Там задача не про это, кость
CD
то есть путь <= 2K это два пути <= K
K
А что не bfs?
KK
Там нужно меньше всего заплатить
KK
Там обычная динама
MB
А что не bfs?
Граф взвешенный
KK
На k слоев
CD
Там обычная динама
а у тебя точно MK log влезет? :))))