洛谷 P1144 最短路计数解题报告

P1144 最短路计数

题目描述

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

输入输出格式

输入格式：

第一行包含2个正整数(N,M)，为图的顶点数与边数。

接下来(M)行，每行2个正整数(x,y)，表示有一条顶点(x)连向顶点(y)的边，请注意可能有自环与重边。

输出格式：

共(N)行，每行一个非负整数，第(i)行输出从顶点1到顶点(i)有多少条不同的最短路，由于答案有可能会很大，你只需要输出(ans) (mod) 100003后的结果即可。如果无法到达顶点(i)则输出0 。

最短路计数，这个用spfa写的。

思路和disj是一样的社交网络

Code:

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N=1000010;
const int mod=100003;
int head[N],to[N<<2],next[N<<2],cnt0;
void add(int u,int v)
{
    next[++cnt0]=head[u];to[cnt0]=v;head[u]=cnt0;
    next[++cnt0]=head[v];to[cnt0]=u;head[v]=cnt0;
}
int n,m,dis[N],used[N],cnt[N];
queue <int > q;
void spfa()
{
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;cnt[1]=1;
    q.push(1);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=next[i])
        {
            int v=to[i];
            if(dis[v]>dis[u]+1)
            {
                 dis[v]=dis[u]+1;
                 cnt[v]=cnt[u];
                 if(!used[v])
                 {
                     used[v]=1;
                     q.push(v);
                 }
            }
            else if(dis[v]==dis[u]+1)
                cnt[v]=(cnt[v]+cnt[u])%mod;
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    int u,v;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    spfa();
    for(int i=1;i<=n;i++)
        printf("%d
",cnt[i]);
    return 0;
}