487. Dijkstra求最短路 II
时间限制：1000 MS 内存限制：64 MB
题目描述
# Dijkstra求最短路 II ## 题目描述 给定一个包含 $n$ 个顶点、$m$ 条边的有向图，顶点编号为 $1$ 至 $n$。图中可能存在重边和自环，所有边权均为非负整数。 请你求出从 $1$ 号点到 $n$ 号点的最短距离，即路径上各条边的边权之和的最小值。如果无法从 $1$ 号点到达 $n$ 号点，则输出 $-1$。 当 $n=1$ 时，起点与终点相同，最短距离为 $0$。 ## 输入格式 从文件 `dijkstras.in` 读入数据。 第一行包含两个整数 $n,m$，分别表示顶点数和边数。 接下来 $m$ 行，每行包含三个整数 $x,y,z$，表示一条从顶点 $x$ 到顶点 $y$、边权为 $z$ 的有向边。 ## 输出格式 输出到文件 `dijkstras.out`。 输出一个整数，表示从 $1$ 号点到 $n$ 号点的最短距离。如果无法到达，则输出 $-1$。 ## 数据范围 - $1 \le n,m \le 150000$。 - $1 \le x,y \le n$。 - $0 \le z \le 10000$，且 $z$ 为整数。 - 图为有向图，允许重边和自环。 ## 样例输入 ``` 3 3 1 2 2 2 3 1 1 3 4 ``` ## 样例输出 ``` 3 ``` ## 样例说明 从 $1$ 号点经过 $2$ 号点到达 $3$ 号点，总距离为 $2+1=3$，小于直接从 $1$ 号点到达 $3$ 号点的距离 $4$，因此最短距离为 $3$。 ## 资源限制 - 时间限制：$1000$ 毫秒。 - 内存限制：$64$ MB。