题解 | 【模板】单源最短路Ⅲ-A ‖ 非负权图：Dijkstra

#include<bits/stdc++.h>
#include <cstring>
#include <queue>
using namespace std;
using ll = long long;
using pii = pair<ll,int>;
const int N = 200010;
int h[N],e[N],ne[N],idx; //定义链表 实现邻接表存储路径
ll w[N]; //权值数组
bool st[N]; //用于表示点到点的距离是否最短
ll dist[N];//用于存储起点到目标点的距离
int n,m,s;
ll u,v,ww;

void add(int a,int b,ll c)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
}

void dijkstra(int s)
{
    memset(dist,0x3f,sizeof dist);
    dist[s] = 0;
    priority_queue<pii,vector<pii>,greater<pii>> hh; //定义优先队列小顶堆 则堆顶为暂未确认的最短距离
    //hh.push({0,s});
    hh.emplace(0,s);
    while(hh.size())
    {
        auto t = hh.top(); //取出堆顶元素
        hh.pop();
        ll distance = t.first   //取出堆中（全局）最小的那一条路的距离
        , ver = t.second;       //取出堆中（全局）最小的那一条路的编号（下标）
        if(st[ver]) continue; //如果该点已确定为最短路径则跳过此次循环，节省时间
        st[ver] = true;       //此时从堆中取出的已是最短路径，标记，不写这一步最后一个检查点会超时1ms！淦

        for(int i=h[ver];i!=-1;i = ne[i]) //此循环用于找到 从起点到遍历到的点 的最短距离
        {                                 //遍历整个邻接表
            int j = e[i];
            if(dist[j] > distance + w[i])//条件判断：当前起点到j点的距离与 distance + w[i]相比
                                         //（w[i]在这里相当于在后半段找了一条新的路）
            {
                dist[j] = distance + w[i];
                //hh.push({dist[j],j});
                hh.emplace(dist[j],j);
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(h, -1, sizeof h);

    cin>>n>>m>>s;
    
    while(m--)
    {
        cin>>u>>v>>ww;
        add(u,v,ww);
    }
    
    dijkstra(s);
    
    for(int i=1;i<=n;i++)
    {
        if(dist[i] > 0x3f3f3f3f3f3f3f3f / 2) cout<<-1<<' ';
        else cout<<dist[i]<<' ';
    }

    return 0;
}