RU
EN
ES
ZH
FR
DE
PT
AR
HI
Поиск кратчайшего пути в графе с использованием классов
PHP
Сложный
classes
Задача «Поиск кратчайшего пути в графе с использованием классов»
Реализуйте класс Graph для представления взвешенного ориентированного графа. Класс должен содержать методы addEdge(int $from, int $to, int $weight) для добавления ребра и shortestPath(int $start, int $end) для нахождения кратчайшего пути от вершины $start до $end с использованием алгоритма Дейкстры. Если пути не существует, метод должен вернуть -1. Гарантируется, что веса ребер положительные, количество вершин не превышает 1000, количество ребер — до 10000.
Формат ввода
В первой строке через пробел заданы N (количество вершин) и M (количество ребер). Далее в M строках заданы ребра: from to weight. В последней строке заданы start и end.
Формат вывода
Целое число — минимальная стоимость пути от start до end, или -1, если пути нет.
Примеры
Пример 1
ВВОД
10
ВЫВОД
87
Пример 2
ВВОД
3 2
1 2 5
2 3 10
1 3
ВЫВОД
15
Пример 3
ВВОД
1
ВЫВОД
0
Пример 4
ВВОД
2 1
1 2 7
2 1
ВЫВОД
-1
main.php