Dijkstra kürzester Pfad-Algorithmus mit Kantenkosten

Question

habe ich ein gerichtetes, positiven gewichteten Graphen. Jede Kante hat ein Nutzungskosten. Ich habe nur ein Geld, ich will kürzesten Wege mit Dijkstra-Algorithmus berechnen, sondern Summe der Kanten Kosten auf der Strecke muss kleiner oder gleich einer.

Ich möchte, dies zu tun mit dem meisten kleinsten Dijstra Modifikation (wenn ich es mit kleiner Modifikation von Dijkstra tun kann). Ich muss dies tun, in O(n*log(n)) wenn ich kann, aber ich denke, ich kann.

Wer kann mir dabei helfen?

Answer 1

https://www.spoj.pl/problems/ROADS/

Das Problem wurde gegeben unter CEOI '98 und seine offizielle Lösung hier .

Answer 2

Sie brauchen nicht wirklich Dijkstra-Algorithmus, dies zu tun, wie die Antwort ist äquivalent zu finden, den kürzesten Weg zu ändern und akzeptiert es dann, wenn es weniger ist als oder gleich A.

Natürlich könnte man immer Kurzschluss die innere Schleife, wenn Sie besuchen einen Pfad mit einem Preis mehr als A.

EDIT: Mit der Klarstellung, dass Sie Kosten und Entfernung minimieren möchten, können Sie das tun, nicht ohne die Lösung zu klären Sie wollen. Haben Sie den günstigsten Weg wollen? Haben Sie den kürzesten Weg wollen? Haben Sie eine Funktion der Kosten und der Abstand wollen? Alle diese Faktoren bestimmen, was Sie Gewichtungsfunktion für eine bestimmte Kante verwendet werden soll.