堆优化版 Dijkstra（Acwing）

                           //处理较大数据用堆优化
/*
  3 3
  1 2 2
  2 3 1
  1 3 4 
 */                        //找到终点距离起点的最短距离
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
                           //堆优化用队列实现
using namespace std;
typedef pair<int,int> PII;  //初始化
const int N=10010;
int he[N],e[N],ne[N],w[N],idx=0;         //新增w存距离
bool st[N];                       //标记走过的点
int dist[N],n,m;
void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=he[a];
    he[a]=idx++;
}
int dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({1,0});                                        //插入节点编号 和 距离
    while(heap.size()) {
        auto t = heap.top();
        heap.pop();
        if (st[t.first])continue;
        st[t.first] = true;
        for (int i = he[t.first]; i != -1; i = ne[i]) {
            if (dist[e[i]] > dist[t.first] + w[i]) {             //也可写成 dist[e[i]]>t.second+w[i]
                dist[e[i]] = dist[t.first] + w[i];
                heap.push({e[i], dist[e[i]]});
            }
        }
    }
        if (dist[n] == 0x3f)
            return -1;
        else
            return dist[n];
    }
int main(void)
{
    memset(he,-1,sizeof he);
    cin>>n>>m;
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    int t=dijkstra();
    cout<<t<<endl;
    return 0;
}