Я получил неориентированный невзвешенный график.Где каждый узел представляет один город.Каждый город производит один тип продуктов (не обязательно должен быть уникальным).Тогда у вас будет на входе несколько типовых продуктов, которые нужно доставить в каждый город.Вы можете перевозить каждый продукт отдельно, и это должен быть кратчайший путь.Расстояние между каждым узлом составляет 1.
На самом деле я использую BFS для каждого узла.Но должно быть лучшее решение.
Example:
INPUT:
5(number of nodes) 5(number of edges)
4(number of groceries) 3(required number of groceries in every city)
0 1 3 2 1 ( city(node number) has grocery 0->0 1->1 2->3 3->2 4->1)
0 1 (edges)
2 1 (edges)
2 3 (edges)
3 0 (edges)
4 3 (edges)
OUTPUT:
11 (total distance)
2(total distance for town) 0 1 2 (groceries in the city)
2 1 0 3
2 3 1 2
2 2 0 1
3 1 2 0