юn вершины иm ненаправленные взвешенные ребра между ними (веса представляют минуты). Каждая вершина содержит количество минут, необходимое для того, чтобы выпить кофе в этой вершине.

Я хочу определить кратчайшее время (минуты), необходимое для получения вершиныv к вершинеw но с дополнительным ограничением, что я должен пить свой кофе именно на одной из вершин на моем пути изv вw).

пример:

(число в вершине - это количество минут, необходимое для того, чтобы выпить кофе, вес по краям представляет количество минут, необходимое для прохождения этого края)

Получить отv вw и выпейте кофе по пути, выведите минимальное необходимое время (должно быть 30).

Мой нынешний подход чтобы найти кратчайший путь с Dijkstra (суммировать веса всех ребер на этом пути), а затем добавить значение вершины с самым низким временем кофе на этом пути к моему результату, чтобы получить общее количество времени, необходимое для получить отv вw.

Мой подход не работает, вот пример, где мой подход терпит неудачу (результат моего подхода - 12 минут, фактический результат должен быть 6 минут):

Как определить кратчайшее время от вершиныv вw с тем ограничением, что мне нужно пить кофе на моем пути?