#O1042. 单源最短路
单源最短路
题目描述
给定 个点、 条带权边的无向图,求从起点 到终点 的最短路长度。若不可达输出 -1。
题目类型
最短路、Dijkstra 堆优化
输入格式
第一行四个整数 。
接下来 行,每行三个整数 ,表示一条权为 的无向边。
输出格式
一行一个整数,表示最短路长度,不可达输出 -1。
样例 #1
样例输入 #1
4 5 1 4
1 2 1
1 3 4
2 3 2
2 4 6
3 4 3
样例输出 #1
6
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 点数 | |
| 边数 | |
| 边权,均为正 |
- 结果需用
long long,用pair<long long,int>的小根堆。