洛谷P4779 题解 单源最短路标准版

Solution

这是一道Dijkstra最短路的模板题

在这里就不说明dj的原理和正确性了（自己查），注意dj仅限于边权为非负的图

还有这题竟然卡SPFA（毒），还是用开了堆优化的dijkstra吧

复杂度是O((n+m))log⁡n)

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int maxm=5e5+10;
bool vis[maxn];
int head[maxn],dis[maxn];
int cnt=0,m,n,s,t;
struct edge{
    int next,to,dis;
}e[maxm];
inline void add_edge(int u,int v,int w)
{
    cnt++;
    e[cnt].dis=w;
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
struct node
{
    int u;
    int id;
    bool operator<(const node &x)const 
    {
        return x.u<u;
    }
};

priority_queue<node> q;
inline void dijkstra()
{
    dis[s]=0;
    q.push((node){0,s});
    while(!q.empty())
    {
        int x=q.top().id;
        q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=e[i].next)
        {
            int y=e[i].to;
            if(dis[y]>dis[x]+e[i].dis)
            {
                dis[y]=dis[x]+e[i].dis;
                q.push((node){dis[y],y});
            }
        }
    }

}

int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=n;i++)
    {
        dis[i]=0x7fffffff;
    }
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add_edge(u,v,w);//注：若是无向图请加上add_edge(v,u,w);
    }
    dijkstra();
    for(int i=1;i<=n;i++)
    {
        printf("%d ",dis[i]);
    }
    return 0;
}