理论nlogn的程序T了两个点

P4779 【模板】单源最短路径(标准版)

XieGuiYi_aic @ 2022-08-05 09:57:25

#include<bits/stdc++.h>
#define visited vd
using namespace std;
struct Edge
{
    int to;
    int w;
    int next;
}edge[314514];
struct node
{
    int w;
    int to;
    bool operator < (const node &a) const{
        return w<a.w;
    }
};
int head[314514],dis[314514],cnt;
bool visited[314514];
priority_queue<node> q;
void add(int u,int v,int w)
{
    cnt++;
    edge[cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
    return;
} 
int read()
{
    char t=getchar();
    int k=0;
    int fushu=1;
    for(;t<'0'||t>'9';t=getchar()) if(t=='-') fushu=-1;
    for(;t>='0'&&t<='9';t=getchar()) k=k*10+(t-'0');
    return k*fushu;
}
void dijkstra(int start)
{
    memset(dis,0x7f,sizeof(dis));
    dis[start]=0;
    q.push((node){0,start});
    while(!q.empty())
    {
        node t=q.top();
        q.pop();
        int k=t.to;
        if(vd[k]==true)
        continue;
        vd[k]==true;
        for(int i=head[k];i;i=edge[i].next)
        {
            if(dis[edge[i].to]>dis[k]+edge[i].w)
            {
                dis[edge[i].to]=dis[k]+edge[i].w;
                if(visited[edge[i].to]==false)
            q.push((node){dis[edge[i].to],edge[i].to});
            }

        }
    }
    return;
}
int n,m,s;
int main()
{
    edge[0].next=-1;
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read(),w=read();
        add(u,v,w);
    }
    dijkstra(s);
    for(int i=1;i<=n;i++)
    cout<<dis[i]<<' ';
    return 0;
}

不知道哪里错了?


by Strelitzia_ @ 2022-08-05 10:08:41

dijkstra 里面第 11vd[k]==true 改成 vd[k]=true


by cfkk @ 2022-08-05 10:12:12

@lnwhl 上课摸鱼!!!!!


by PRIMITIVE_LIGHTS @ 2022-08-05 10:18:09

priority初始是大根堆


by PRIMITIVE_LIGHTS @ 2022-08-05 10:18:28

bool operator < (const node &a) const{
        return w>a.w;
    }

这样就可以了


by PRIMITIVE_LIGHTS @ 2022-08-05 10:18:34

@Strelitzia_


by Strelitzia_ @ 2022-08-05 10:20:04

@qwq_volcano 您是不是 @ 错人了


by XieGuiYi_aic @ 2022-08-05 10:21:41

谢谢,已A


by PRIMITIVE_LIGHTS @ 2022-08-05 10:27:36

@Strelitzia_ 好吧


|