В оригинальном условии задачи ограничение на количество вершин N ≤ 10.
В разборе к этой задаче есть упражнение: решить задачу для N ≤ 50 c помощью динамического программирования.
Подскажите, пожалуйста, как решить задачу при N ≤ 50.
В оригинальном условии задачи ограничение на количество вершин N ≤ 10.
В разборе к этой задаче есть упражнение: решить задачу для N ≤ 50 c помощью динамического программирования.
Подскажите, пожалуйста, как решить задачу при N ≤ 50.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
Не знаю насчёт ДП, но возведением матрицы в степень, кажется, её можно решить.
Случай, когда C <= кратчайшего пути между v1 и v2 — тривиальный, также как и случай, когда пути нет вообще. Пусть C > кратчайшего пути. Возведем матрицу в степень C и посмотрим на (i, j) элемент. Если там не ноль, то путь длины C есть, и ответ "Yes 0". Если там ноль, то есть путь длины C+1 (можно дойти до конечной вершины и дальше крутиться вокруг неё) и ответ "No 1".
UPD Я затупил, последнее верно только для неориентированного графа. С ориентированным вроде можно проверить 50 соседних степеней матрицы влево и 50 вправо :)
Действительно, я как-то сразу не додумался что ответ, если он существует, будет лежать либо недалеко от C, либо в каких-то маленьких степенях матрицы ( ≤ 50).
Спасибо!
Если уж придраться к терминологии, то возведение матрицы в степень — способ ускорения подсчета частного случая ДП.