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 
    
     #include 
     
      #include 
      
       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 
       
         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\n",cnt[i]);    return 0;}
       
      
     
    

---

2018.7.1