P1144 最短路计数

题目描述

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

输入输出格式

输入格式：

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

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

输出格式：

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

输入输出样例

输入样例#1：

5 71 21 32 43 42 34 54 5

输出样例#1：

说明

1到5的最短路有4条，分别为2条1-2-4-5和2条1-3-4-5（由于4-5的边有2条）。

对于20%的数据，N ≤ 100；

对于60%的数据，N ≤ 1000；

对于100%的数据，N<=1000000，M<=2000000。

变形的spfa（说白了就是一个bfs），在进行最短路查询的时候判断是否出现了距离相同的路径。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define N 2000000#define mod 100003using namespace std;queue
          
           q;bool vis[N];int n,m,x,y,tot,head[N],ans[N],dis[N];int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f;}struct Edge{ int to,next,from;}edge[N<<1];int add(int x,int y){ tot++; edge[tot].to=y; edge[tot].next=head[x]; head[x]=tot;}int main(){ n=read(),m=read(); for(int i=1;i<=m;i++) x=read(),y=read(),add(x,y),add(y,x); memset(dis,0x3f3f3f3f,sizeof(dis)); q.push(1),dis[1]=0,vis[1]=true;ans[1]=1; while(!q.empty()) { x=q.front();q.pop();vis[x]=false; for(int i=head[x];i;i=edge[i].next) { int to=edge[i].to; if(dis[to]>dis[x]+1) { dis[to]=dis[x]+1; ans[to]=ans[x]%mod; if(!vis[to]) { vis[to]=true; q.push(to); } } else if(dis[to]==dis[x]+1) { ans[to]=(ans[x]+ans[to])%mod; if(!vis[to]) { vis[to]=true; q.push(to); } } } } for(int i=1;i<=n;i++) printf("%d\n",ans[i]); return 0;}

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              using namespace std;struct Edge//邻接表存边{ int t; int nexty;}edge[3000000];int head[2000000]={ 0};//邻接表的东东（存以i为发出点的编号最大的边的编号）……有人不懂吗int cnt=0;inline void add(int a,int b)//邻接表添加边{ cnt++; edge[cnt].t=b; edge[cnt].nexty=head[a]; head[a]=cnt;}int js[2000000]={ 0};//每一个点的最短路径条数int rdjs[2000000]={ 0};//用来避免重复的统计表，存当前在队列中，到节点i的最短路径条数int dis[2000000];//存最短路径bool in[2000000]={ 0};//是否在队列中queue
              
               spfa;//SPFA所用队列int main(){ int n,m; scanf("%d%d",&n,&m); int a,b; for(int i=0;i
               
                dis[curr]+1)//若最短路有变 { dis[edge[i].t]=dis[curr]+1;//更新最短路 rdjs[edge[i].t]=js[edge[i].t]=rdjs[curr]%100003;//以前的计数均舍弃，更新到出发点的到达路径条数 if(!in[edge[i].t]) { //加入队列 in[edge[i].t]=true; spfa.push(edge[i].t); } } else if(dis[edge[i].t]==dis[curr]+1)//若又有一条最短路 { js[edge[i].t]=(js[edge[i].t]+rdjs[curr])%100003;//增加最短路个数 rdjs[edge[i].t]=(rdjs[edge[i].t]+rdjs[curr])%100003;//在rdjs上更新，避免重复 if(!in[edge[i].t]) { //入队 in[edge[i].t]=true; spfa.push(edge[i].t); } } } in[curr]=false; rdjs[curr]=0;//此次的最短路统计已用完，将此节点的最短路条数初始化，避免重复（在此题中似乎并没有什么用） spfa.pop();//出队 } for(int i=1;i<=n;i++)printf("%d\n",js[i]);//输出 return 0;}