Buenas, encarando esta parte no logramos entender como hacer para no pasarnos de tiempo al encontrar la arista de costo máximo, ya leimos la solución pero no la entendimos.
Gracias.
Hola.
Creo que quedó claro en la clase de consulta, pero por las dudas agrego algunos apuntes.
No se busca una arista de costo máximo.
Creo que quedó claro en la clase de consulta, pero por las dudas agrego algunos apuntes.
No se busca una arista de costo máximo.
Para cada arista (u,v)
- se obtienen el camino más corto desde s a u, y el camino más corto desde v a t
- se suman los costos de esos dos caminos con lo que se obtiene el costo del camino más corto que pasa por (u,v) si se la eligiera como comodín
- la arista para el cual esa suma sea mínima es la que se elige como comodín.
El camino más corto desde s a cada u se obtiene con una ejecución de Dijkstra. Para obtener el camino más corto dese cada v a t y mantener el orden pedido (es decir sin ejecutar Dijkstra desde cada vértice, lo que implicaría costo 
) es que se ejecuta Dijkstra, una sola vez, desde t en el grafo traspuesto.
) es que se ejecuta Dijkstra, una sola vez, desde t en el grafo traspuesto. Después de haber hecho las dos corridas de Dijkstra se recorre cada arista, haciendo la suma indicada más arriba. El costo de procesar cada arista es O(1). Entonces el recorrido de las aristas en O(m + n).
Si algo no quedó claro volvé a preguntar.