求图中的最短路径生成树有多少个？ （ 该生成树中的任意点i ，i到1的距离和  原图中的i到1的最短距离相等

 

 跑所有点到1的单源最短路，d[i]

 if d[i]==d[y]+z ，那么z这个路径是该生成树的一条边

然后就是多步计数，乘法原理即可

 

#include <iostream>
#include <cstring>
#include <queue>
using namespace std ; 
 #define int long long
 struct T{
     int y,z;
     T(int y0,int z0){
         y=y0,z=z0;
     }
     bool operator<(T a)const{
         return z>a.z;
     }
 };
 const int N=1e4+1,M=1e6+1,inf=0x3f3f3f3f;
 const int mod=(1<<31)-1;
 int n,b[N],d[N],nxt[M],w[M],go[M],hd[N],all;
 int m;
 int cnt[N];
 void add(int x,int y,int z){
     go[++all]=y,nxt[all]=hd[x]; hd[x]=all,w[all]=z;
 }
 priority_queue<T> q;
 
 void dijk(int v0){
     int i,x,y,z;
     memset(d,inf,sizeof d); d[v0]=0;
     q.push(T(v0,0));
     
     while(q.empty()==0){
         x=q.top().y,q.pop(); if(b[x]) continue;
         b[x]=1;
         for(i=hd[x];i;i=nxt[i]){
             y=go[i],z=w[i]; 
             if(d[x]+z<d[y]){
                 d[y]=d[x]+z; q.push(T(y,d[y]));
            }
         }
     }
 }
 void solve(){
     int i,j,x,y,z;
     for(i=1;i<=m;i++) cin>>x>>y>>z,add(x,y,z),add(y,x,z);
     
     dijk(1);
     for(i=1;i<=n;i++)
      for(j=hd[i];j;j=nxt[j]){
          y=go[j]; if(d[y]==d[i]+w[j]) cnt[y]++;
      }
      int ans=1;
      for(i=2;i<=n;i++) ans*=cnt[i],ans%=mod;
      cout<<ans;
 }
 signed main(){
     cin>>n>>m;
     solve();
 }

 

原文地址：http://www.cnblogs.com/towboa/p/16880237.html

1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！ 2. 分享目的仅供大家学习和交流，请务用于商业用途! 3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！ 4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！ 5. 如有链接无法下载、失效或广告，请联系管理员处理！ 6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！ 7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！ 8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载 声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性