Мотаясь по различным делам из одной точки в другую, заметил, что маршруты дел могут накрываться и что для некоторого списка дел можно придумать оптимальный маршрут по контрольным точкам так, чтобы выполнить все дела, затратив наименьшее количество усилий.

Теперь более официальное условие задачи: есть связный взвешенный неориентированный граф без петель и кратных ребер. Также есть список дел. Требуется из данной вершины S придти в F, при этом выполнив все дела из списка. Дело представляет из себя пару чисел s_i и f_i — номера вершин в графе, для каждого дела нужно сначала посетить s_i, а затем посетить f_i. Надо вывести длину минимального пути из S в F, который покрывает все дела, а также сам этот путь. Пусть будет N вершин, M ребер и K дел. Нужно найти самое оптимальное решение. UPD1: Дела необязательно делать последовательно, можно выполнять несколько дел одновременно в любом порядке, в этом и смысл задачи.

Прошу помочь в решении этой задачи, потому что стало интересно, а сам додуматься не смог. Также прошу прощения, если это где-то уже обсуждалось или же за формулировкой задачи скрыто что-то совсем простое, а я не заметил.

UPD2: в комментариях было сказано про метод отжига, статьи о нем можно почитать здесь. Я, если честно, не очень понял, если кто-то может подробно его описать на примере этой задачи, я буду очень благодарен.