Dijkstra(单源最短路径算法)

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f
#define pb push_back
#define mem(a,x) memset(a,x,sizeof(a))


struct node
{
    int x, dis;

    // 运算符重载（将对列中存的元素按长度从小到大排）
    bool operator < (const node &p) const
    {
        return p.dis < dis;
    }
};

int n, m, s;
vector<node>e[100010];  // 存图（包含路径长度）
int vis[100010];        // 标记是否访问
int dis[100010];        // 起点到各个点的最短路

priority_queue<node>q;  // 优先队列存储待处理边
void Dij()
{
    dis[s] = 0;         // 起点最短路为0
    q.push((node){s,0});// 将起点压入队列
    while(!q.empty())
    {
        node a = q.top();   // 取队列头元素
        q.pop();
        int x = a.x;
        if(vis[x]) continue;    // 访问过的点continue
        vis[x] = 1;             // 标记访问
        for(int i = 0; i < e[x].size(); i++)    // 更新最短路
        {
            node y = e[x][i];   // 相连节点
            // 与x相连的节点y的当前最短距离大于x的最短距离加上x到y的距离，更新y的最短距离
            if(!vis[y.x]&&dis[y.x]>dis[x]+y.dis){
                dis[y.x] = dis[x]+y.dis;
                q.push((node){y.x,dis[y.x]});// 节点压入队列
            }
        }
    }
}   

int main()
{
    mem(vis,0);
    mem(dis,INF);
    cin >> n >> m >> s;
    int u, v, w;
    // 建图
    for(int i = 0; i < m; i++)
    {
        cin >> u >> v >> w;
        e[u].pb((node){v,w});
    }
    Dij(); 
    for(int i = 1; i <= n; i++) cout << dis[i] << " ";
    return 0;
}