c++蒟蒻求助dijkstra

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

Jason12 @ 2022-03-01 20:19:44

样例无输出,return value 3221225477

#include <bits/stdc++.h>
  using namespace std;
int n,m,l,t,a[100005],c[100005],u,v,w,i,j;
bool d[100005];
struct xy{
    int x,y,z;
}b[200005];
void add(int u,int v,int w)
{
    b[++l].x=a[u];
    a[u]=l;
    b[l].y=v;
    b[l].z=w;
    return;
}
int main()
{
    scanf("%d%d%d",&n,&m,&t);
    memset(a,0x3f,sizeof(a));
    a[t]=0;
    d[t]=1;
    for (i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        if (u==t) c[v]=w;
    }
    for (i=1;i<=n;i++)
    {
        u=0x3f3f3f3f;
        for (j=1;j<=n;j++)
        {
            if (!d[j] && u>c[j])
            {
                u=c[j];
                v=j;
            }
        }
        d[v]=1;
        for (j=a[v];j;j=b[j].x)
        {
            c[j]=min(c[j],c[v]+b[j].z);
        }
    }
    for (i=1;i<n;i++)
    {
        printf("%d ",c[i]);
    }
    printf("%d\n",c[n]);
    return 0;
}

by LYqwq @ 2022-03-01 20:24:01

标准版要加堆优化


by LYqwq @ 2022-03-01 20:24:17

这个 dij 几乎过不了题


by Missa @ 2022-03-01 20:24:19

@Jason12 你的 a 数组看着是链式前向星的 head 数组,那就不要赋初值,否则

for (j=a[v];j;j=b[j].x)

会越界


by Missa @ 2022-03-01 20:24:44

另外你dij复杂度不对


by Jason12 @ 2022-03-01 20:33:58

@璇___ @LYqwq 谢谢大佬们!Thanks♪(・ω・)ノ


|