Module: Dijkstra-Algorithmus


Problem

2 /14


Dijkstra

Theory Click to read/hide

Problem

Es wurde ein orientiertes gewichtetes Diagramm angegeben. Finden Sie den kürzesten Abstand von einem bestimmten Scheitelpunkt zum anderen.
 
Eingabe
Die erste Zeile enthält drei Zahlen: N, S und F (1≤ N≤ 100, 1≤ S, F≤ N), wobei N – die Anzahl der Eckpunkte des Graphen, S – der Anfangsscheitelpunkt und F – der Endpunkt ist. In den nächsten N Zeilen werden N Zahlen eingegeben, die nicht größer als 100 sind, – die Adjazenzmatrix des Graphen, wobei -1 bedeutet, dass keine Kante zwischen den Eckpunkten fehlt und jede nicht negative Zahl die Anwesenheit einer Kante dieses Gewichts ist. Auf der Hauptdiagonale der Matrix sind Nullen geschrieben.
Ausgabe
Sie möchten den gewünschten Abstand oder -1 anzeigen, wenn kein Pfad zwischen den angegebenen Scheitelpunkten vorhanden ist.

Beispiele
№ Eingabe Ausgabe
1
3 2 1
0 1 1
4 0 1
2 1 0
 3

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!