Mana Collection
El editorial oficial ofrece una solución completa para este problema, pero hay algunos detalles a los que conviene prestar atención.
Hacer un Floyd-Warshall al comienzo del algoritmo es necesario porque, aunque la DP con máscaras de bits enumera el siguiente nodo no visitado, puede ser óptimo o incluso necesario pasar por un nodo que ya visitamos para llegar allí.
Por ejemplo, consideremos la siguiente lista de adyacencia:
1 -> 2
2 -> 1
1 -> 3Para ir del nodo 2 al nodo 3, tenemos que pasar por el nodo 1 de todas formas.
Además, puede parecer más intuitivo definir la DP con máscaras de bits como dp[mask][i],
donde mask representa los nodos que hemos visitado actualmente (en orden inverso),
e i representa el nodo en el que estamos.
El problema de esta definición, sin embargo, es que nuestro estado no tiene idea de cuál es el conjunto final de nodos visitados, lo que significa que no tenemos forma de calcular con precisión el efecto de atravesar una arista.