一. 题目

二. 思路

三. 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
using namespace std;
const int N=1.5*1e5+10;
const int INF=2e9;

int n, m;

class SingleLinkedList
{
public:
    int h[N], e[N], w[N], ne[N], idx;
public:
    SingleLinkedList()
    {
        initIO(), idx=0;
        fill(h, h+N, -1);
        fill(e, e+N, 0);
        fill(w, w+N, 0);
        fill(ne, ne+N, 0);
    }

    void initIO()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr), cout.tie(nullptr);
    }

    //a到b间添加一条边，边值为c
    void add(int a, int b, int c)
    {
        e[idx]=b, w[idx]=c;
        ne[idx]=h[a], h[a]=idx++;
    }
}sll;

class Dijkstra
{
public:
    class Node
    {
        public:
            int id, d;//点编号，距离源点的距离
        public:
            Node(int id_, int d_):id(id_), d(d_) {}
    
            bool operator < (const Node &t) const
            {               //默认priority_queue用vector实现
                return d>t.d;//priority_queue默认大根堆，用元素<号判断大小
                //此处重载为d>t.d是小，则d<t.d时是大
                //因为默认大根堆，此时弹出较小的d, 相当于优先队列变成了小根堆
            }
    };
    
public:
    int dist[N];//点距离源点的最短距离
    bool st[N];//判断点是否已求出最短路
    priority_queue<Node> q;//优先队列
public:
    Dijkstra()
    {
        fill(dist, dist+N, INF);
        fill(st, st+N, false);
    }

    int work()
    {
        dist[1]=0;
        q.emplace(1, 0);

        while(!q.empty())
        {
            auto t=q.top();
            q.pop();

            if(t.id==n) break;//n出来，表示找到最短路
            if(st[t.id]) continue;//当前点已经是求出最短路的点
            st[t.id]=true;//第一次出来就是最短的

            for(int i=sll.h[t.id];~i;i=sll.ne[i])
            {
                int j=sll.e[i];
                if(dist[j]>t.d+sll.w[i])
                {
                    dist[j]=t.d+sll.w[i];
                    q.emplace(j, dist[j]);
                }
            }
        }

        return dist[n];
    }
}d;

int main()
{
    cin>>n>>m;
    while(m--)
    {
        int a, b, c;
        cin>>a>>b>>c;
        sll.add(a, b, c);
    }

    int ans=d.work();
    if(ans==INF) cout<<"-1";
    else cout<<ans;
}