Dijkstra 单源最短路径

【模板】单源最短路径（标准版）

步骤

把一个结点和它的dist封装成node，建立关于node的优先权队列，dist小的优先级大。
1.把源点入队；
2.从队首取出一个元素，更新它所指向的结点的最短dist，并把更新后的结点入队，直至队空。
更新结点这一操作也叫做松弛操作。

优先权队列的作用：当一个结点被放入队列，并且被当成队首拿出来访问过一次之后，它的dist就已经是最短了，不会再更新了，队列里可能还会有这个点，但队列里现存的这个点的dist都是旧的，而且不是最短，无效，访问到的时候直接vis标记跳过就行。
这个vis标记是用来进行懒惰删除的。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1e5+10, maxm = 5e5+5, inf = 2147483647;
typedef struct Edge{
    int from,to,weight;
    int next;
}Edge;
typedef struct node{
    int dist;
    int pos;
    bool operator < (const node &x) const{
        return x.dist < dist;
    }
}node;
int n,m,s;
int dist[maxn],vis[maxn];
int head[maxn];
int tot;
Edge e[maxm];
priority_queue<node> q;
void AddEdge(int from,int to,int weight){
    tot++;
    e[tot].from = from;
    e[tot].to = to;
    e[tot].weight = weight;
    e[tot].next = head[from];
    head[from] = tot;
}
int main(){
    int from,to,weight;
    cin >> n >> m >> s;
    for (int i=1;i<=n;i++){
        dist[i] = head[i] = inf;
        vis[i] = 0;
    }
    for (int i=1;i<=m;i++){
        cin >> from >> to >> weight;
        AddEdge(from,to,weight);
    }
    node tmp;
    q.push((node){0,s});
    dist[s] = 0;
    while (!q.empty()){
        tmp = q.top();    q.pop();
        if (vis[tmp.pos])   continue;
        vis[tmp.pos] = 1;
        for (int i=head[tmp.pos];i!=inf;i=e[i].next){
            if (dist[e[i].to] > dist[tmp.pos]+e[i].weight){
                dist[e[i].to] = dist[tmp.pos]+e[i].weight;
                q.push((node){dist[e[i].to], e[i].to});
            }
        }
    }
    for (int i=1;i<=n;i++)
        cout << dist[i] << " ";
    return 0;
}