valeriikozlov

Niсe, У Вас реализацию поиска в ширину. Для этой задачи любой существующий алгоритм в оригинальном виде не подойдет. Нужно переделывать его под эту задачу.
Представьте себе вершину (допустим через нее проходит самый короткий путь) - в которую входят 3 дуги (по одной каждого цвета) и из которой выходят 3 дуги (по одной каждого цвета). Допустим Вы дошли быстрее всего в эту вершину через дугу цветом 1. Вы ее помечаете, и идете дальше по двум дугам: 2 и 3 цветов. Путь в эту же вершину через дугу 2 хоть и дольше чем через дугу 1, но он дает возможность идти дальше из этой вершины по дуге 1 и в итоге может оказаться что это и есть самый короткий путь.
Для этой задачи подойдет поиск в ширину, но:
- рассматривайте вершину не как единое целое, а как три разных составляющих (по цветам). Например вершину 4, рассматривайте как: (4,1), (4,2), (4,3). Здесь второе число считается номером цвета. Для каждой такой составляющей будет свое значение. Например: (4,1)=15, (4,2)=15, (4,3)=17. Это будет значить, что вершину 4 по дугам 1 и 2 цвета мы достигли за 15 шагов, а по дуге цветом 3, мы достигли за 17 шагов.
Изначально помещайте в очередь не просто вершину n-1, а вот так: (n-1,1), (n-1,2), (n-1, 3), поставив им метки 0 (будем считать, что вершину, из которой начинаем путь мы по всем вершинам достигли за 0 шагов).
Далее алгоритм такой:
Из очереди берете очередной элемент, например: (4,2). Смотрите смежные вершины с 4 вершиной, (например смежная вершина 3). Если смежная вершина соединена не дугой цветом 2 (например цветом 1), то: (3,1), если она не помечена, помечаете значением (4,2)+1 и заносите в очередь.
В конце этого алгоритма проверяете значения (0,1), (0,2), (0,3). Если все три значения не помечены, то ответ: -1. Если нет, то ответ минимальное значение из трех.

Вернуться к обсуждению:
Покрашенный граф C++

1