> For the complete documentation index, see [llms.txt](https://851958789.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://851958789.gitbook.io/notes/0743_network_delay_time/slt.md).

# Solution1 Dijkstra + 邻接矩阵

* 时间复杂度 O(n^3)

    朴素 Dijkstra O(n^2) \* 枚举其他的点 O(n)
* 空间复杂度 O(n^2)

求的是「从 k 点出发，所有点都被访问到的最短时间」，将问题转换一下其实就是求「从 k 点出发，到其他点 x 的最短距离的最大值」。

以 k 作为原点，枚举其他所有点作为汇点，求最短路。取其中的 max，即是最后的结果。