队列优化的dijkstra

#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef pair<int, int> pii;
const int maxn=1e5+5, maxm=2e5+5;
struct edge
{
    int t, w; edge * nxt;
    edge(int to, int len, edge * next){ t=to, w=len, nxt=next; }
};
edge * head[maxn];
void add(int u, int v, int len){ head[u]=new edge(v, len, head[u]); }
int dis[maxn], v[maxn], n, m, s;

void dijkstra(int s)
{
    memset(dis, 0x3f, sizeof dis);                          //sizeof不是一个函数，而是运算符，这种用法是可以的
    priority_queue<pii, vector<pii>, greater<pii> > Q;      //小根堆 
    dis[s]=0;
    Q.push(make_pair(0, s));
    while(!Q.empty())
    {
        int x=Q.top().second;
        if(v[x]) { Q.pop(); continue;}                      //continue;之前一定要pop掉，否则会死循环 
        else     { v[x]=true; dis[x]=Q.top().first; Q.pop();}

        for(edge *p=head[x]; p; p=p->nxt)   if (!v[p->t])   Q.push(make_pair(dis[x]+p->w, p->t));
    }
}

int main()
{
    scanf("%d%d%d", &n, &m, &s);
    for(int i=1, x, y, z; i<=m; i++)    scanf("%d%d%d", &x, &y, &z), add(x, y, z);
    dijkstra(s);
    for(int i=1; i<=n; i++)             printf("%d ", dis[i]);
    printf("\n");
    return 0;
}

队列优化的dijkstra

原文：https://www.cnblogs.com/lfyzoi/p/10481106.html