最短路计数——Dijkstra-白红宇

最短路计数——Dijkstra

阅读量：4971 次

发布时间：2019-06-12

本文共 1732 字，大约阅读时间需要 5 分钟。

题目：

　　给出一个

　　1.无向无权图，建图的时候别忘记建来回的有向边

　　2.无权，那么边长建成1就好了

　　3.最短路采用 Dijkstra（堆优化）来做，计数操作改装进去，tot[1]=1;用 Dijkstra 更新边长的时候如果大于号（具体见代码）就覆盖，相等的话就加上。

AC代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                #include
                 
                  #include
                  
                   using namespace std;#define maxn 2000005#define mod 100003int head[maxn],vis[maxn],d[maxn],tot[maxn];int cnt=0,n,m,s;priority_queue
                   
                    
                     ,vector
                     
                      
                        >,greater
                       
                        
                          > >q;struct hh{ int nex,to;}t[maxn<<1];inline void add(int nex,int to){ t[++cnt].nex=head[nex]; t[cnt].to=to; head[nex]=cnt;}inline int read(){ char kr=0; char ls; for(;ls>'9'||ls<'0';kr=ls,ls=getchar()); int xs=0; for(;ls>='0'&&ls<='9';ls=getchar()) { xs=xs*10+ls-48; } if(kr=='-') xs=0-xs; return xs;}inline void dijkstra(){ memset(d,0x3f,sizeof(d)); memset(tot,0,sizeof(tot)); memset(vis,0,sizeof(vis)); q.push(make_pair(0,1)); d[1]=0; vis[1]=1; tot[1]=1; while(!q.empty()) { int u=q.top().second; q.pop(); vis[u]=0; for(int v=head[u];v;v=t[v].nex) { if(d[t[v].to]>d[u]+1) { d[t[v].to]=d[u]+1; tot[t[v].to]=tot[u]; if(!vis[v]) { q.push(make_pair(d[t[v].to],t[v].to)); vis[v]=1; } continue; } else if(d[t[v].to]==d[u]+1) { tot[t[v].to]+=tot[u];//tot记录的是点上的数，不是边上。（查了好久） tot[t[v].to]%=mod; continue; }//关键是这两个 if 语句，其它的跟单源最短路没什么区别 } }}int main(){ n=read();m=read(); int x,y; for(int i=1;i<=m;i++) { x=read();y=read(); add(x,y); add(y,x); } dijkstra(); for(int i=1;i<=n;i++) { printf("%d\n",tot[i]); }return 0;}