DE
RU
EN
ES
ZH
FR
PT
AR
HI
Suche nach dem kürzesten Pfad in einem Graphen mit Klassen
PHP
Hard
classes
Aufgabe «Suche nach dem kürzesten Pfad in einem Graphen mit Klassen»
Implementieren Sie die Klasse Graph zur Darstellung eines gewichteten gerichteten Graphen. Die Klasse muss die Methoden addEdge(int $from, int $to, int $weight) zum Hinzufügen einer Kante und shortestPath(int $start, int $end) zur Ermittlung des kürzesten Pfades vom Knoten $start zum Knoten $end mithilfe des Dijkstra-Algorithmus enthalten. Wenn kein Pfad existiert, soll die Methode -1 zurückgeben. Es wird garantiert, dass die Kantengewichte positiv sind, die Anzahl der Knoten 1000 nicht überschreitet und die Anzahl der Kanten bis zu 10000 beträgt.
Eingabeformat
In der ersten Zeile werden durch Leerzeichen getrennt N (Anzahl der Knoten) und M (Anzahl der Kanten) angegeben. Danach folgen in M Zeilen die Kanten: from to weight. In der letzten Zeile werden start und end angegeben.
Ausgabeformat
Eine ganze Zahl – die minimalen Kosten des Pfades von start nach end, oder -1, wenn kein Pfad vorhanden ist.
Beispiele
Beispiel 1
EINGABE
10
AUSGABE
87
Beispiel 2
EINGABE
3 2
1 2 5
2 3 10
1 3
AUSGABE
15
Beispiel 3
EINGABE
1
AUSGABE
0
Beispiel 4
EINGABE
2 1
1 2 7
2 1
AUSGABE
-1
main.php