求大佬帮忙

回复帖子

@zhengjinchen 2020-11-22 11:43 回复

Dijkstra 我在从 O(n²) 优化到 O(n log n)时候写挂了

求大佬帮忙,谢谢

//O(n log n)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
inline int getint()
{
    char ch=getchar();long long w=0,f=1;
    while(ch<'0' || ch>'9'){if(ch=='-')f=-f; ch=getchar();}
    while(ch>='0' && ch<='9'){w=(w<<1)+(w<<3)+(ch^48); ch=getchar();}
    return w*f;
}

int n,m,tot,start;
const int MAXN=500005;
struct Edge
{
    int u,w,head,nxt;
}a[MAXN];
struct Point
{
    int dis,number;
    bool operator < (const Point &a)const
    {
        return dis<a.dis;
    };
}p[MAXN];
inline bool cmp(Point x,Point y)
{
    return x.dis<y.dis;
}
priority_queue<Point> q;

void add(int x,int y,int v)
{
    tot++;
    a[tot].u=y;
    a[tot].w=v;
    a[tot].nxt=a[x].head;
    a[x].head=tot;
}
inline void Dijkstra(int start)
{
    for(register int i=1;i<=n;i++)
    {
        p[i].number=i;
        q.push(p[i]);
    }
    for(register int i=1;i<=n;i++)
    {
        Point minn=q.top();q.pop();
        int mini=minn.number;
        for(register int j=a[mini].head;j;j=a[j].nxt)
            p[a[j].u].dis=min(p[a[j].u].dis,p[mini].dis+a[j].w);
    }
    p[start].dis=0;
    for(int i=1;i<=n;i++)
    {
        if(p[i].dis!=1000000000) cout<<p[i].dis<<" ";
        else cout<<2147483647<<" ";
    }
}
int main()
{
    for(int i=1;i<MAXN-5;i++) p[i].dis=1000000000;
    n=getint();m=getint();start=getint();
    for(register int i=1;i<=m;i++)
    {
        int u,v,w;
        u=getint();v=getint();w=getint();
        add(u,v,w);
        if(u==start) p[v].dis=w;
    }
    p[start].dis=0;
    Dijkstra(start);
    return 0;
}
//O(n²)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
inline int getint()
{
    char ch=getchar();long long w=0,f=1;
    while(ch<'0' || ch>'9'){if(ch=='-')f=-f; ch=getchar();}
    while(ch>='0' && ch<='9'){w=(w<<1)+(w<<3)+(ch^48); ch=getchar();}
    return w*f;
}
const int MAXN=500005;
int u[MAXN],w[MAXN],dis[MAXN],head[MAXN],nxt[MAXN],tot;
bool vis[MAXN];
void add(int x,int y,int v)
{
    tot++;
    u[tot]=y;
    w[tot]=v;
    nxt[tot]=head[x];
    head[x]=tot;
}
int n,m,start;
inline void Dijkstra(int start)
{
    for(register int i=1;i<=n;i++)
    {
        int minn=1e9,mini;
        for(register int j=1;j<=n;j++)
        {
            if(!vis[j] && minn>dis[j])
            {
                minn=dis[j];
                mini=j;
            }
        }
        vis[mini]=true;
        for(register int j=head[mini];j;j=nxt[j])
            dis[u[j]]=min(dis[u[j]],dis[mini]+w[j]);
    }
    dis[start]=0;
    for(int i=1;i<=n;i++)
    {
        if(dis[i]!=1061109567) cout<<dis[i]<<" ";
        else cout<<2147483647<<" ";
    }
}
int main()
{
    memset(dis,0x3f3f3f,sizeof(dis));
    n=getint();m=getint();start=getint();
    for(register int i=1;i<=m;i++)
    {
        int u,v,w;
        u=getint();v=getint();w=getint();
        add(u,v,w);
        if(u==start) dis[v]=w;
    }
    dis[start]=0;
    Dijkstra(start);
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。