#O1042. 单源最短路

单源最短路

题目描述

给定 nn 个点、mm 条带权边的无向图,求从起点 ss 到终点 tt 的最短路长度。若不可达输出 -1。

题目类型

最短路、Dijkstra 堆优化

输入格式

第一行四个整数 n,m,s,tn, m, s, t。

接下来 mm 行,每行三个整数 u,v,wu, v, w,表示一条权为 ww 的无向边。

输出格式

一行一个整数,表示最短路长度,不可达输出 -1。

样例 #1

样例输入 #1

4 5 1 4
1 2 1
1 3 4
2 3 2
2 4 6
3 4 3

样例输出 #1

6

数据规模与约定

数据范围 说明
1≤n≤2×1051 \le n \le 2 \times 10^5 点数
0≤m≤4×1050 \le m \le 4 \times 10^5 边数
1≤w≤1061 \le w \le 10^6 边权,均为正
  • 结果需用 long long,用 pair<long long,int> 的小根堆。