dij 不知道为什么错 谁能帮我调一下

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

chasing_dream @ 2022-07-04 21:45:20

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    register int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<3)+(x<<1)+(c^48); 
        c=getchar();
    }
    return x*f;
}
const int maxn=1e5+10;
const int maxm=2e5+10;
const int inf=0x7f;
struct edge
{
    int dis,next,to;
}a[maxm];
struct node
{
    int d,p;//d是距离,u是当前节点  
    bool operator <( const node &x )const
    {
        return x.d<d;
    }
};
int dis[maxn],head[maxn],n,m,s,cnt;
bool vis[maxn];
priority_queue<node>q;
void addedge(int u,int v,int w)
{
    cnt++;
    a[cnt].dis=w;
    a[cnt].to=v;
    a[cnt].next=head[u];
    head[u]=cnt;
}
int main()
{
    n=read(),m=read(),s=read();
    for(int i=1;i<=n;i++) dis[i]=inf;
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read(),w=read();
        addedge(u,v,w);
    }
    dis[s]=0;
    q.push((node){0,s});
    while(!q.empty())
    {
        node tmp=q.top();
        q.pop();
        int u=tmp.p;
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[i];i;i=a[i].next)
        {
            if(dis[a[i].to]>dis[u]+a[i].dis)
            {
                dis[a[i].to]=dis[u]+a[i].dis;
                if(!vis[a[i].to])
                    q.push((node){dis[a[i].to],a[i].to});   
            }
        }
    }
    for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
    return 0;
}

by qwasd @ 2022-07-04 21:49:48

@chasing_dream priority_queue 默认大根堆,所以 return x.d<d; 应该改成 return x.d>d;


by chasing_dream @ 2022-07-04 21:51:32

@qwasd 还错


by Anonymely @ 2022-07-04 21:54:45

@chasing_dream

i=a[i].i

错了吧


by chasing_dream @ 2022-07-04 21:56:25

@trisomy 在哪里


by Anonymely @ 2022-07-04 22:02:30

@chasing_dream

for(int i=head[i];i;i=a[i].next)

by chasing_dream @ 2022-07-04 22:11:35

@trisomy 改成了i=head[u] 样例过了,但是还是错


by a16_ @ 2022-07-04 22:31:11

@chasing_dream inf=1e9


by a16_ @ 2022-07-04 22:32:42

还有,重载运算符不用改


by chasing_dream @ 2022-07-05 10:53:17

@上清沦谪 谢谢!


|