dijkstradijkstra堆优化3TLE求调教（悬关注）

_AyachiNene @ 2023-03-16 22:01:21

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int nxt,val,to;
}a[114514*2];
int head[114514],n,m,s,cnt,dist[114514];
bool vis[114514];
priority_queue<pair<int,int> >q; 
void add(int x,int y,int z)
{
    a[++cnt].to=y;
    a[cnt].val=z;
    a[cnt].nxt=head[x];
    head[x]=cnt;
}
void djs(int s)
{
    for(int i=1;i<=n;i++)
        dist[i]=INT_MAX;
    dist[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        s=q.top().second;
        vis[s]=1;
        q.pop();
        for(int i=head[s];i;i=a[i].nxt)
        {
            int x=a[i].to;
            if(dist[x]>dist[s]+a[i].val&&!vis[x])
                dist[x]=dist[s]+a[i].val,q.push(make_pair(-dist[x],x));
        }
    }
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int u,v,z;
        scanf("%d%d%d",&u,&v,&z);
        add(u,v,z);
    }
    djs(s);
    for(int i=1;i<=n;i++)
        printf("%d ",dist[i]);
}

by Ruiqun2009 @ 2023-03-16 22:15:14

@brother_jie INT_MAX 做运算会溢出。

by _AyachiNene @ 2023-03-16 22:20:39

@Ruiqun2009 这和tle没有关系吧

by Ruiqun2009 @ 2023-03-16 22:23:11

@brother_jie

1. 把 INT_MAX 换成 0x3f3f3f3f
2. 循环内部应该判断是否访问过这个节点，如果访问过就跳过

by _AyachiNene @ 2023-03-16 22:38:57

@Ruiqun2009 还是会t啊

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int nxt,val,to;
}a[114514*2];
int head[114514],n,m,s,cnt,dist[114514];
bool vis[114514];
priority_queue<pair<int,int> >q; 
void add(int x,int y,int z)
{
    a[++cnt].to=y;
    a[cnt].val=z;
    a[cnt].nxt=head[x];
    head[x]=cnt;
}
void djs(int s)
{
    for(int i=1;i<=n;i++)
        dist[i]=0x3f3f3f3f;
    dist[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        s=q.top().second;
        vis[s]=1;
        q.pop();
        for(int i=head[s];i;i=a[i].nxt)
        {
            int x=a[i].to;
            if(vis[x])
                continue;
            if(dist[x]>dist[s]+a[i].val)
            {
                dist[x]=dist[s]+a[i].val;
                if(!vis[x])
                    q.push(make_pair(-dist[x],x)); 
            }
        }
    }
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int u,v,z;
        scanf("%d%d%d",&u,&v,&z);
        add(u,v,z);
    }
    djs(s);
    for(int i=1;i<=n;i++)
        printf("%d ",dist[i]);
}

by Ruiqun2009 @ 2023-03-16 22:40:28

@brother_jie 不是你那个意思。

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int nxt,val,to;
}a[114514*2];
int head[114514],n,m,s,cnt,dist[114514];
bool vis[114514];
priority_queue<pair<int,int> >q; 
void add(int x,int y,int z)
{
    a[++cnt].to=y;
    a[cnt].val=z;
    a[cnt].nxt=head[x];
    head[x]=cnt;
}
void djs(int s)
{
    for(int i=1;i<=n;i++)
        dist[i]=0x3f3f3f3f;
    dist[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty())
    {
        s=q.top().second;
        q.pop();//***
        if(vis[s])continue;//***
        vis[s]=1;
        for(int i=head[s];i;i=a[i].nxt)
        {
            int x=a[i].to;
            if(dist[x]>dist[s]+a[i].val&&!vis[x])
                dist[x]=dist[s]+a[i].val,q.push(make_pair(-dist[x],x));
        }
    }
}
int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int u,v,z;
        scanf("%d%d%d",&u,&v,&z);
        add(u,v,z);
    }
    djs(s);
    for(int i=1;i<=n;i++)
        printf("%d ",dist[i]);
}

by _AyachiNene @ 2023-03-16 22:42:37

@Ruiqun2009 dalao这事为什么啊，我是把没访问过的点存进队列里的，怎么这么写就能对a

by Xuan_ @ 2023-09-12 16:31:51

有没有一种可能性：虽然放进队列时还没有访问到，但是从队列取出来的时候已经访问到了。这里是优先队列。