优先队列dijkstra TLE求调

jixiaolong @ 2024-10-21 22:46:32

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=1e5+1;

priority_queue<pair<int,int> >q;
int m,n,tot,s;
int head[N],Next[N],ver[N],edge[N],d[N];
bool v[N];

void add(int x,int y,int z)
{
    ver[++tot]=y;
    edge[tot]=z;
    Next[tot]=head[x];
    head[x]=tot;
    return ;
}

void dijkstra(int sx)
{
    memset(d,0x3f,sizeof(d));
    d[sx]=0;
    q.push(make_pair(0,sx));
    while(q.size())
    {
        int x=q.top().second;
        q.pop();
        if(v[x]) continue;
        v[sx]=1;
        for(int i=head[x];i;i=Next[i])
        {
            int y=ver[i],z=edge[i];
            if(d[y]>d[x]+z)
            {
                d[y]=d[x]+z;
                q.push(make_pair(-d[y],y));
            }
        }
    }
    return ;
}

int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    dijkstra(s);
    for(int i=1;i<=n;i++)
    {
        cout<<d[i]<<" ";
    }
    return 0;
}

by wwwidk1234 @ 2024-10-21 23:40:38

@jixiaolong

/*
算法：priority_queued Dijkstra
思路：https://www.luogu.com.cn/discuss/969037
我是嘉明和那维莱特的____！
*/
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=1e5+10;
const int M=2e5+10;   //一共有M=2e5条边,边数组开1e5会炸

priority_queue<pair<int,int> > q;
int m,n,tot,s;
int head[N],Next[M],ver[M],edge[M],d[N];
bool v[N];

void add(int x,int y,int z)
{
    ver[++tot]=y;
    edge[tot]=z;
    Next[tot]=head[x];
    head[x]=tot;
    return ;
}

void dijkstra(int sx)
{
    memset(d,0x3f,sizeof(d));
    d[sx]=0;
    q.push(make_pair(0,sx));
    while(q.size())
    {
        int x=q.top().second;
        q.pop();
        if(v[x]) continue;
        // v[sx]=1; //这里你应该是打错了,标记应该标记相同的点
        v[x]=1;
        for(int i=head[x];i;i=Next[i])
        {
            int y=ver[i],z=edge[i];
            if(d[y]>d[x]+z)
            {
                d[y]=d[x]+z;
                q.push(make_pair(-d[y],y));
            }
        }
    }
    return ;
}

int main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    dijkstra(s);
    for(int i=1;i<=n;i++)
    {
        cout<<d[i]<<" ";
    }
    return 0;
}

by wwwidk1234 @ 2024-10-21 23:40:55

@jixiaolong 数组开小了，标记打错了

by jixiaolong @ 2024-10-22 22:47:55

@wwwidk1234 AC了，谢谢dalao