El problema dado se puede dividir en 2 subproblemas:
- Dado un gráfico, cómo encontrar todos los bordes que vienen en cualquiera de las rutas más cortas del gráfico.
- Al encontrar la ruta más corta en el gráfico donde tiene 2, elimine los bordes mencionados anteriormente.
Parte 1: utilice el algoritmo de dijkstra para mantener 2 matrices dis1 y dis2 donde dis1 [i] representa la distancia del nodo i desde el origen y dis2 [i] representa la distancia del nodo desde el destino. Ahora mantenga todos los nodos que se visitan en la ruta más corta. (si para un nodo i dis1 [i] + dis2 [i] == dis1 [destino] {distancia más corta}, debería incluirse). Todos los bordes cuyos extremos están en el camino más corto son los bordes que necesitamos marcar.
Complejidad: O (e * log (v) + v + e)
- ¿Cómo se vinculan los nodos al mismo nivel en un árbol binario?
- Cómo escribir un validador de sangría de Python
- ¿Qué tan difícil es el algoritmo de verificación de traducción de Duolingo? ¿Existen otras herramientas de código abierto similares por ahí?
- ¿Estamos utilizando los mismos algoritmos de inteligencia artificial de los años 90 con mejores procesadores?
- ¿Por qué no necesito conocer algoritmos para lenguajes de programación modernos como Java o Python?
Parte 2: aplique nuevamente el algoritmo de dijkstra, pero al insertar vecinos en la cola de prioridad, verifique que si el borde pertenece al conjunto de bordes marcados (en caso afirmativo, omítalo).
Complejidad: O (e * log (v))
Complejidad general: O (e * log (v))
Aquí está mi solución aceptada: Ideone.com (eche un vistazo si está atascado)
¡Espero eso ayude! 🙂
