注意是无向图，且宽搜的时候，不需要st数组

三种最短路的求法
1. BFS：一层一层扩展，每次扩展一层，必然是按拓扑序列求。每个点只入队一次，且只出队一次
2. DJK：保证每个点只作为最小值出队一次。当一个点出来的时候，他就不可能更新前面出现过的点。每个点第一次出队的序列，必然满足拓扑序
3. SPFA：每个点可能出队多次，出队之后也有可能更新前面的点，本身不具备拓扑序

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N=100010,M=400010,mod=100003;

int n,m;
int h[N],e[M],ne[M],idx;
int st[N],dist[N],cnt[N];

void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

void bfs()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;
    cnt[1]=1;
    queue<int> q;
    q.push(1);
    while(q.size())
    {
        int t =q.front();
        q.pop();
        //bfs，不需要st数组
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+1)
            {
                dist[j]=dist[t]+1;
                cnt[j]=cnt[t];
                q.push(j);
            }
            else if(dist[j]==dist[t]+1)
            {
                cnt[j]=(cnt[j]+cnt[t])%mod;
            }

        }
    }
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);

    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    bfs();
    for(int i=1;i<=n;i++)
    {
        cout<<cnt[i]<<endl;
    }

    return 0;
}

二刷

其实不需要用到st数组，因为做bfs时，第一次遍历到这个点，一定是最小距离了，之后无论如何都不会进入

if(dist[j]>dist[t]+1)

因此用不用st都一样

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N=100010,M=400010,mod=100003;

int n,m;
int h[N],e[M],ne[M],idx;
int st[N],dist[N],cnt[N];


void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

int bfs()
{
    memset(dist,0x3f,sizeof dist);
    memset(st,0,sizeof st);
    queue<int> q;
    cnt[1]=1;
    dist[1]=0;
    st[1]=1;
    q.push(1);

    while(q.size())
    {
        int t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+1)
            {
                dist[j]=dist[t]+1;
                cnt[j]=cnt[t];
                if(!st[j])
                {
                    st[j]=1;
                    q.push(j);
                }
            }
            else if(dist[j]==dist[t]+1)
            {
                cnt[j]=(cnt[j]+cnt[t])%mod;
            }
        }

    }

}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    bfs();
    for(int i=1;i<=n;i++)
    {
        cout<<cnt[i]<<endl;
    }

    return 0;
}

三刷，刚开始当成有向边做了

总结一下思路：
1. 因为无边权，所以可以直接用bfs做，第一次遍历到的一定是最小的距离
2. 后来如果再次遍历到点j，如果是由点t遍历到他，且dist[t]+1=dist[j]，则cnt[j]+=cnt[t];

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;
const int N=1000010;
const int mod=100003;

int h[N],e[N*2],ne[N*2],st[N],dist[N],idx;
int cnt[N];
int n,m;

void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}

void top()
{
    memset(dist,0x3f,sizeof dist);
    queue<int> q;
    q.push(1);
    dist[1]=0;
    cnt[1]=1;


    while(q.size())
    {
        int t=q.front();
        q.pop();
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]==0x3f3f3f3f)
            {
                dist[j]=dist[t]+1;
                cnt[j]=(cnt[j]+cnt[t])%mod;
                q.push(j);
            }
            else if(dist[j]==dist[t]+1)
            {
                cnt[j]=(cnt[j]+cnt[t])%mod;
            }
        }
    }
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    top();
    for(int i=1;i<=n;i++)
    {
        cout<<cnt[i]<<endl;
    }
    return 0;
}

2023/12/3

一遍过, 注意数据范围
和173 矩阵距离相似

利用BFS性质: 第一次遍历到一定是最短的

因为要求最短路个数，所以不能设置st数组，不能说一个点已经被确定了最短路就不去遍历它(djk)。还是要遍历它的，看看有没有相等的路径，要加上

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N=400010;
const int mod = 100003;

int e[N],ne[N],h[N];
int idx;
int st[N],cnt[N],dist[N];
int n,m;

void add(int a,int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

int bfs()
{
    memset(dist, 0x3f, sizeof(dist));
    memset(st, 0, sizeof(st));

    queue<int> q;
    q.push(1);
    dist[1] = 0;
    cnt[1] = 1;


    while(q.size())
    {
        int t=q.front();
        q.pop();


        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];


            // bfs性质: 第一次遍历到一定是最短的
            if(dist[j] > dist[t]+1)
            {
                dist[j] = dist[t] + 1;
                cnt[j] = cnt[t]%mod;
                q.push(j);
            }
            else if(dist[j] == dist[t] + 1)
            {
                cnt[j] = (cnt[j]+cnt[t])%mod;
            }
        }
    }

}


int main()
{
    cin>>n>>m;
    memset(h, -1, sizeof(h));
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }

    bfs();

    for(int i=1;i<=n;i++)
    {
        cout<<cnt[i]<<endl;
    }

    return 0;
}