486. Dijkstra求最短路 I
时间限制：1000 MS 内存限制：64 MB
题目描述
# Dijkstra求最短路 I ## 题目描述 给定一个有 $n$ 个点、$m$ 条边的有向图，顶点编号为 $1$ 到 $n$。图中可能存在重边和自环，所有边权均为正整数。 请你求出从 $1$ 号点到 $n$ 号点的最短距离。路径的长度为路径上所有边的权值之和。如果无法从 $1$ 号点到达 $n$ 号点，则输出 $-1$。 当 $n=1$ 时，最短距离为 $0$。 ## 输入格式 从文件 `dijkstra.in` 中读入数据。 第一行包含两个整数 $n,m$，分别表示顶点数和边数。 接下来 $m$ 行，每行包含三个整数 $x,y,z$，表示存在一条从 $x$ 号点到 $y$ 号点的有向边，权值为 $z$。 ## 输出格式 将结果输出到文件 `dijkstra.out` 中。 输出一个整数，表示从 $1$ 号点到 $n$ 号点的最短距离。如果无法到达，则输出 $-1$。 ## 数据范围 - $1 \le n \le 500$。 - $1 \le m \le 100000$。 - $1 \le x,y \le n$。 - $1 \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。