LG-1144

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

思路

无权，其实可以看做是边权为 $1$ 。

那么只需要跑一边 SPFA ，过程中如果一个点 $v$ 的最短路被点 $u$ 更新了，那么到点 $v$ 的最短路数目等于到点 $v$ 的最短路数目；相等的话则直接累加。

如此即可。

代码

#include<bits/stdc++.h>
#define N 1000010
#define mod 100003

using namespace std;

inline int read() {
    int w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int n,m;

int head[N],tot=0;
struct grpah{
    int v,w,next;
}edge[N<<1];
void add_edge(int u,int v,int w) {
    edge[++tot].v=v;
    edge[tot].w=w;
    edge[tot].next=head[u];
    head[u]=tot;
}
void add(int u,int v,int w) {add_edge(u,v,w),add_edge(v,u,w);}

int dis[N],cnt[N];
bool vh[N];
queue<int> q;
void SPFA(int s) {
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;
    cnt[s]=1;
    q.push(s);
    vh[s]=true;
    while(!q.empty()) {
        int u=q.front();q.pop();
        vh[u]=false;
        for(int i=head[u];i;i=edge[i].next) {
            int v=edge[i].v,w=edge[i].w;
            if(dis[u]<dis[v]-w) {
                dis[v]=dis[u]+w;
                cnt[v]=cnt[u];
                if(!vh[v]) {
                    q.push(v);
                    vh[v]=true;
                }
            }
            else if(dis[u]==dis[v]-w) (cnt[v]+=cnt[u])%=mod;
        }
    }
}

int main() {
    n=read(),m=read();
    for(int i=1;i<=m;i++) {
        int u=read(),v=read();
        if(u==v) continue;
        add(u,v,1);
    }  
    SPFA(1);
    for(int i=1;i<=n;i++) printf("%d\n",cnt[i]);
    system("pause");
    return 0;
}