Searching for the shortest path in a graph using classes

PHP Hard classes

任务 «Searching for the shortest path in a graph using 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。

输出格式

<p>一个整数——从 start 到 end 的最小路径成本，如果不存在路径则返回 -1。</p>

示例

示例 1

输入

10

输出

87

示例 2

输入

输出

15

示例 3

输入

1

输出

0

示例 4

输入

1
2 7
1

输出

-1

main.php