Dijkstra算法
1、每次找出离源点最近的节点，此时的节点离源点的距离就是节点离源点的最短距离

2、更新从该节点拓展的节点，并且与原来该节点离源点的距离进行比较，更新为较小值

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5;
typedef pair<int,int> PII;//存储到源点的距离，以及点的编号
int n,m;
int h[N],w[N],e[N],ne[N],idx;//邻接表存储图
int dist[N];//存储距离
bool st[N];//存储状态，标记是否已经找到最短距离
void add(int a,int b,int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int Dijkstra(){
    memset(dist, 0x3f , sizeof dist);//初始化距离为无穷大
    dist[1] = 0;//源点距离为0
    priority_queue<PII,vector<PII>,greater<PII>> heap;//小根堆，vector是存储堆元素的容器
    heap.push({0,1});//将源点加入堆中

    while(heap.size()){
        auto t = heap.top();//获得离源点最近的点
        heap.pop();
        int ver = t.second, dis = t.first;//ver表示当前节点的序号 dis表示当前节点离源点的 距离
        if(st[ver]) continue;//如果该点已经找到了最小距离，则跳过
        st[ver] = 1;

        for(int i = h[ver]; i != -1; i = ne[i]){//将从该点拓展的节点的距离更新
            int j = e[i];//序号
            if(dist[j] > dis + w[i]){
                dist[j] = dis + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}
int main(){
    cin >> n >> m;
    memset(h , -1 , sizeof h);
    for(int i = 0; i < m; i++){
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
    }
    cout << Dijkstra() << endl;
    return 0;
}