题目描述

给出一个N个顶点M条边的无向无权图，顶点编号为1～N。问从顶点1开始，到其他每个点的最短路有几条。

思路

因为是无权边，所以第一个走到的肯定是最短的，然后在spfa中开一个记录的数组，每次走到一个路程等于它的就加上来的那个点有多少种方法
O(KE)

#include <stdio.h>
#include <queue>
#define maxn 2000001
#define mod 100003
using namespace std;
int l=0;
struct arr 
{ 
    int x,y,w,next; 
};
arr edge[maxn];
int state[maxn],ls[maxn],f[maxn];
bool exits[maxn];
int spfa()
{
    int i;
    queue <int> t;
    t.push(1);
    state[1]=0;
    exits[1]=true;
    do
    {
        int tt=t.front();
        t.pop();
        i=ls[tt];
        while (i!=0) 
        {
            if (state[edge[i].x]+edge[i].w<=state[edge[i].y])
            {
                f[edge[i].y]+=1*f[edge[i].x];
                f[edge[i].y]%=mod;
                state[edge[i].y]=state[edge[i].x]+edge[i].w;
                if (exits[edge[i].y]==false)
                {
                    t.push(edge[i].y);
                    exits[edge[i].y]=true;
                }
            }
            i=edge[i].next;
        }
        exits[tt]=false;
    }
    while (!t.empty());
}
int main()
{
    int j,k,n,m,s;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        l++;
        int x,y;
        scanf("%d%d",&x,&y);
        edge[l].x=x; edge[l].y=y; edge[l].w=1; edge[l].next=ls[edge[l].x]; ls[edge[l].x]=l;
        l++;
        edge[l].x=y; edge[l].y=x; edge[l].w=1; edge[l].next=ls[edge[l].x]; ls[edge[l].x]=l;
    }

    for (int i=1;i<maxn;i++)
        state[i]=0xfffffff;
    f[1]=1;   
    spfa();
    for (int i=1;i<=n;i++)
        printf("%d\n",f[i]);
}