README ¶ 850. Dijkstra求最短路 II 题目 给定一个 $n$ 个点 $m$ 条边的有向图,图中可能存在重边和自环,所有边权均为非负值。 请你求出 $1$ 号点到 $n$ 号点的最短距离,如果无法从 $1$ 号点走到 $n$ 号点,则输出 $-1$。 输入格式 第一行包含整数 $n$ 和 $m$。 接下来 $m$ 行每行包含三个整数 $x,y,z$,表示存在一条从点 $x$ 到点 $y$ 的有向边,边长为 $z$。 输出格式 输出一个整数,表示 $1$ 号点到 $n$ 号点的最短距离。 如果路径不存在,则输出 $-1$。 数据范围 $1 \le n,m \le 1.5 \times 10^5$, 图中涉及边长均不小于 $0$,且不超过 $10000$。 输入样例: 3 3 1 2 2 2 3 1 1 3 4 输出样例: 3 题解 前置题目:0849 前置知识:堆 本题知识:搜索与图论-Dijkstra 题目分析 堆优化版的Dijkstra算法 适用条件:所有边权都是正数的单源最短路问题 时间复杂度:O(mlogn) Expand ▾ Collapse ▴ Documentation ¶ There is no documentation for this package. Source Files ¶ View all Source files 0850-Dijkstra求最短路II.go Click to show internal directories. Click to hide internal directories.