ES
RU
EN
ZH
FR
DE
PT
AR
HI
Búsqueda del camino más corto en un grafo utilizando clases
PHP
Hard
classes
Tarea «Búsqueda del camino más corto en un grafo utilizando clases»
Implemente la clase Graph para representar un grafo dirigido ponderado. La clase debe contener los métodos addEdge(int $from, int $to, int $weight) para agregar una arista y shortestPath(int $start, int $end) para encontrar el camino más corto desde el vértice $start hasta $end utilizando el algoritmo de Dijkstra. Si no existe un camino, el método debe devolver -1. Se garantiza que los pesos de las aristas son positivos, el número de vértices no supera 1000 y el número de aristas llega hasta 10000.
Formato de entrada
En la primera línea, separados por espacio, se indican N (número de vértices) y M (número de aristas). Luego, en M líneas se indican las aristas: from to weight. En la última línea se indican start y end.
Formato de salida
Un número entero — el costo mínimo del camino desde start hasta end, o -1 si no hay camino.
Ejemplos
Ejemplo 1
ENTRADA
10
SALIDA
87
Ejemplo 2
ENTRADA
3 2
1 2 5
2 3 10
1 3
SALIDA
15
Ejemplo 3
ENTRADA
1
SALIDA
0
Ejemplo 4
ENTRADA
2 1
1 2 7
2 1
SALIDA
-1
main.php