Algorithmus zur Berechnung der kürzesten Zeit, in der zwei Personen K Objekte aus N Städten sammeln können

Question

Es gibt N Städte, die über M bidirektionale Straßen verbunden sind. Jede Straße verbindet genau 2 verschiedene Städte und hat damit eine Reisezeit.

In diesen Städten gibt es K verschiedene Artikel. Angesichts der Liste der Gegenstände in jeder Stadt. Zwei Menschen stehen in der Stadt Nummer 1. Sie beide müssen alle K Gegenstände in kürzester Zeit bekommen. Um dies zu tun, beschließen sie, den Einkauf zwischen sich auf die folgende Weise zu teilen.

Beide Leute wählten ihre eigenen Wege, beginnend bei Stadt 1 und endend bei Stadt N. Sie müssen nicht notwendigerweise die gleichen Wege nehmen. Während der Reise sammelt jeder von ihnen Gegenstände in bestimmten Städten. Wenn beide Leute Stadt N erreichen, müssen sie alle K Gegenstände gesammelt gekauft haben. Wenn eine Person vor der anderen endet, wartet er in der Stadt N, bis sein Partner fertig ist. Das heißt, die Gesamtzeit ist das Maximum ihrer jeweiligen Fahrzeiten. Jede Person kann Stadt N besuchen dazwischen, aber sie haben beide ihre Wege in Stadt N. zu beenden

Answer 1

ich nicht sicher bin, ob es korrekt ist, aber wir können auf diese Weise vorgehen:

seit Gesamtfahrzeit beträgt max (t_1, t_2) wo t_i ist die Reisezeit von cat_i, so dass wir zuerst den Graphen (Baum) mit dem Dijkstra-Algorithmus fahren, während wir feststellen, welche Arten von Fischen gesammelt wurden ... Nachdem cat1 fertig ist, beginnt cat2 seine Traversierung Wird eine bestimmte Kante zurückgelegt, wenn der andere Endpunkt Fischarten enthält, die nicht gesammelt wurden.Wenn es mehr als einen solchen Kandidaten gibt, wird der Pfad mit niedrigen Kosten ausgewählt