// 这是对1的优化,主要优化在什么地方呢?
// 不用迭代n-1次在循环两次n次分别找最小点和最想点接近的点
// 采用用优先队列的堆来储存已经更新过的点和dist,直接调用top就能找到最小点
// 然后遍历它自己有关的边就可以了不用全部遍历所有点了
// 其他思路相同
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 150010;
// 稀疏图用邻接表来存
int h[N], e[N], ne[N], idx;
int w[N]; // 用来存权重
int dist[N];
bool st[N]; // 如果为true说明这个点的最短路径已经确定
int n, m;
void add(int x, int y, int c)
{
// 有重边也不要紧,假设1->2有权重为2和3的边,再遍历到点1的时候2号点的距离会更新两次放入堆中
// 这样堆中会有很多冗余的点,但是在弹出的时候还是会弹出最小值2+x(x为之前确定的最短路径),
// 并标记st为true,所以下一次弹出3+x会continue不会向下执行。
w[idx] = c;
e[idx] = y;
ne[idx] = h[x];
h[x] = idx++;
}
int dijkstra()
{
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap; // 定义一个小根堆
// 这里heap中为什么要存pair呢,首先小根堆是根据距离来排的,所以有一个变量要是距离,
// 其次在从堆中拿出来的时候要知道知道这个点是哪个点,不然怎么更新邻接点呢?所以第二个变量要存点。
heap.push({ 0, 1 }); // 这个顺序不能倒,pair排序时是先根据first,再根据second,
// 这里显然要根据距离排序
while(heap.size())
{
PII k = heap.top(); // 取不在集合S中距离最短的点
heap.pop();
int ver = k.second, distance = k.first;
if(st[ver]) continue;
st[ver] = true;
for(int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i]; // i只是个下标,e中在存的是i这个下标对应的点。
if(dist[j] > distance + w[i])
{
dist[j] = distance + w[i];
heap.push({ dist[j], j });
}
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
else return dist[n];
}
int main()
{
memset(h, -1, sizeof(h));
scanf("%d%d", &n, &m);
while (m--)
{
int x, y, c;
scanf("%d%d%d", &x, &y, &c);
add(x, y, c);
}
cout << dijkstra() << endl;
return 0;
}