求助,bfs只AC了最后一个点
查看原帖
求助,bfs只AC了最后一个点
445049
Winkle楼主2021/10/30 13:54

不知道为什么会输出0

#include <iostream>
#include <cstdio>
using namespace std;
int dl[2000001]={};//bfs队列
struct las//每个点最短路的结构体
{
    int duan;//最短路长度
    int num;//个数
}zd[1000001];//数组
struct bia//邻接表存边
{
    int from;
    int to;
    int nex;
    bool use=false;
}bian[2000001];
struct hed
{
    int fir;
    int las;
    int num;
}head[1000001];
int p=0;
void lian(int a,int b)//连边
{
    p++;
    if(head[a].num)
    {
        bian[head[a].las].nex=p;
        head[a].las=p;
        head[a].num++;
        bian[p].from=a;
        bian[p].to=b;
    }
    else
    {
        head[a].fir=head[a].las=p;
        head[a].num=1;
        bian[p].from=a;
        bian[p].to=b;
    }
}
int main()
{
//数据读入与处理
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        if(a==b)
            continue;
        lian(a,b);
        lian(b,a);
    }
    int hd=1;
    int tl=2;
    dl[1]=1;//队列1为开头
    zd[1].duan=0;
    zd[1].num=1;//1的最短路是0,只有1种
    //bfs
    while(tl>hd)//bfs
    {
        for(int i=head[hd].fir;i;i=bian[i].nex)
        {
            if((zd[bian[i].to].duan!=0&&zd[bian[i].to].duan<=zd[bian[i].from].duan)||bian[i].to==1)//如果最短路被更新了并且现在的深度比最短路大,或这条边指向1,continue
                continue;
            else
            {
             //   printf("%d %d %d\n",dl[hd],bian[i].to,bian[i].from);
                zd[bian[i].to].duan=zd[bian[i].from].duan+1;//最短路长度(bfs第一次进搜索树就是最短路)
                zd[bian[i].to].num+=zd[bian[i].from].num;//最短路个数
                zd[bian[i].to].num%=100003;
                dl[tl]=bian[i].to;//队列设置
                tl++;

            }
        }
        hd++;
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d\n",zd[i].num);
    }//输出
    return 0;
}

2021/10/30 13:54
加载中...