Solución oficial

Para resolver solo el requisito a), solo se mantendrán en el grafos aquellos bordes que el dragón puede atravesar en la isla 1 (que tienen una longitud menor que la distancia máxima Dmáx [1]). Luego, se realizará una exploración BFS o DFS desde el nodo 1 en este grafos para determinar el conjunto M de nodos que se pueden visitar a partir del nodo 1 utilizando solo el dragón 1. La respuesta será el valor máximo Dmax [x] para el cual x pertenece a M.

Para resolver el requisito b), construiremos un nuevo grafos en el que podamos representar correctamente los movimientos que Hiccup puede hacer. Por lo tanto, un nodo estará representado por un par (i, j) (1 <= i, j <= N), con el siguiente significado: Hipo está en el nodo i que tiene un dragón de tipo j. Luego dibujaremos los bordes en este nuevo grafos correspondiente a los movimientos que Hiccup puede hacer:

1. Vuelo:

Para cada borde del grafos inicial A [i], B [i], D [i] y cada j entre 1 y N, tenemos un borde bidireccional en el nuevo grafos entre los nodos (A [i], j), (B [i ], j) de longitud D [i] solo si D [i] <= Dmax [j]. Este borde corresponde a un vuelo entre los nodos A [i] y B [i] con el dragón j.

1. Cambiando el dragón:

Para cada nodo i en el grafos original y cada j entre 1 y N, tenemos un borde unidireccional entre los nodos (i, j) e (i, i) de costo 0 en el nuevo grafos. Este borde corresponde al cambio de un dragón arbitrario j con un dragón de la especie en el nodo i.

En este grafos recién construido, el algoritmo de Dijkstra se aplicará a partir del nodo (1, 1). La solución será la distancia mínima a la que podemos acceder a uno de los nodos (N, 1), (N, 2) ... (N, n), porque no estamos interesados ??en qué dragón tenemos en el nodo N.

Vale la pena mencionar que el grafos no debe retenerse efectivamente en la memoria, ya que este enfoque no cae dentro de los límites del problema. Observe que para cualquier i entre 1 y M y cualquier j entre 1 y N, tenemos (A [i], j) -> (B [i], j) en el nuevo grafos solo si D [i] <= Dmax [j ]: esta verificación se puede hacer dentro del algoritmo de Dijkstra cuando intentamos ver si un borde puede mejorar cierta distancia. Los bordes de tipo (i, j) -> (i, i) pueden generarse nuevamente en el camino, sin tener que ser retenidos.

Complejidad de tiempo: tiempo O (M * N log N), memoria O (N + M).

Solución alternativa (para el requisito 2) - Adrián Panaete

Considere la multitud de todas las parejas isla-dragón. Para cada par, la distancia mínima recorrida se calcula para alcanzar la isla respectiva con el dragón respectivo. Inicialmente, solo tenemos el dragón 1 en la isla 1 con distancia 0. A continuación, siempre elegiremos el par de distancia mínima disponible. Corresponderá a una isla y un dragón.

Es mejor elegir entre el dragón respectivo y el dragón correspondiente a la isla e intentará mejorar las distancias a los vecinos de la isla que se encuentran a una distancia menor que Dmax para ese dragón. Para mantener los pares ordenados, se puede utilizar una estructura de tipo conjunto o montón. Para evitar el uso de dicha estructura, se puede utilizar el principio del algoritmo Bellman-Ford. Más precisamente, se mantiene una cola con todos los pares en los que se ha producido una mejora de la distancia y se procesan los elementos en la cola. Para mayor eficiencia, se puede marcar un par en la entrada de la cola y demarcarlo al salir de este.

Si la isla de destino es incluso la isla N, en lugar de insertar el par en la cola, la solución se actualiza.