yo tengon vértices ym bordes ponderados no dirigidos entre ellos (los pesos representan minutos). Cada vértice contiene una cantidad de minutos necesarios para tomar un café en ese vértice.

Quiero determinar la menor cantidad de tiempo (minutos) necesaria para obtener desde el vérticev al vérticew pero con la restricción adicional de que tengo que tomar mi café exactamente en uno de los vértices en mi camino desdev aw)

Ejemplo:

(el número en el vértice es la cantidad de minutos necesarios para tomar un café, los pesos en los bordes representan la cantidad de minutos necesarios para recorrer este borde)

Llegar desdev aw y beba un café en su camino, genere el tiempo mínimo necesario (la producción debe ser 30).

Mi enfoque actual es encontrar el camino más corto con Dijkstra (resumir los pesos de todos los bordes en ese camino) y luego agregar el valor del vértice con el menor tiempo de café en ese camino a mi resultado para obtener la cantidad total de tiempo necesario para llegar desdev aw.

Mi enfoque no funciona, aquí hay un ejemplo en el que falla mi enfoque (el resultado de mi enfoque es de 12 minutos, el resultado real debería ser de 6 minutos):

Cómo determinar la menor cantidad de tiempo desde el vérticev aw con la restricción de que necesito tomar un café en mi camino?