有边权的无向图，求最短路径树的方案数

思路

同样的思路，用 cnt[v] 记录节点的最短路方案数，最后乘起来就行了

// 最短路径树 Dijkstra 算法 O(MlogN)
#include<bits/stdc++.h>
#define ll long long
#define pli pair<ll,int>
using namespace std;

const int N=1010,M=N*N;
const ll mod=2147483647;
int h[N],to[M],ne[M],idx; ll ww[M];
void add(int a,int b,ll c){
  to[++idx]=b,ww[idx]=c,ne[idx]=h[a],h[a]=idx;
}
int n,m;
ll d[N],cnt[N]; bool vis[N];

void dijkstra(){
  for(int i=1; i<=n; i++) d[i]=1e18; d[1]=0;
  priority_queue<pli,vector<pli>,greater<pli> >q;
  q.push({0,1});
  while(!q.empty()){
    auto u=q.top().second; q.pop();
    if(vis[u]) continue; vis[u]=1;
    for(int i=h[u]; i; i=ne[i]){
      int v=to[i],w=ww[i];
      if(d[v]>d[u]+w){
        d[v]=d[u]+w;
        q.push({d[v],v});
        cnt[v]=1;
      }
      else if(d[v]==d[u]+w) cnt[v]++;
    }
  }
}
int main(){
  scanf("%d%d",&n,&m);
  for(int i=0; i<m; i++){
    int a,b; ll c;
    scanf("%d%d%lld",&a,&b,&c);
    add(a,b,c),add(b,a,c);
  }
  dijkstra();
  ll ans=1;
  for(int i=2; i<=n; i++) ans=ans*cnt[i]%mod;
  printf("%lld\n",ans);
}

//堆优化dijkstra153ms：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII; 
const int N=1010;
const LL P=(1ll<<31)-1;
vector<PII>G[N];
int n,m,d[N],vis[N],sum[N];
void dijkstra()
{
    priority_queue<PII,vector<PII>,greater<PII>>q;
    memset(d,63,sizeof(d));d[1]=0;
    memset(vis,0,sizeof(vis));
    q.push({0,1});
    while(!q.empty())
	{
        int x=q.top().second;q.pop();
		if(vis[x])continue;
		vis[x]=1;
        for(auto i:G[x])
		{
            int y=i.first,w=i.second;
            if(d[y]>d[x]+w)
			{
                d[y]=d[x]+w;
                q.push({d[y],y});
            }
        }
    }   
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,x,y,w;i<=m;i++)
	{
        scanf("%d%d%d",&x,&y,&w);
        G[x].emplace_back(PII(y,w));
        G[y].emplace_back(PII(x,w));
    }
    dijkstra();
    memset(sum,0,sizeof(sum));
    for(int x=1;x<=n;x++)
	{
        for(auto i:G[x])
		{
            int y=i.first,w=i.second;
            if(d[x]+w==d[y])sum[y]++;
        }
    }
    LL ans=1;
    for(int i=2;i<=n;i++)ans=ans*sum[i]%P;
    printf("%lld",ans);
    return 0;
}

//spfa163ms：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII; 
const int N=1010;
const LL P=(1ll<<31)-1;
vector<PII>G[N];
int n,m,d[N],vis[N],sum[N];
void spfa()
{
    priority_queue<PII,vector<PII>,greater<PII>>q;
    memset(d,63,sizeof(d));d[1]=0;
    memset(vis,0,sizeof(vis));vis[1]=1;
    q.push({0,1});
    while(!q.empty())
	{
        int x=q.top().second;q.pop();vis[x]=0;
        for(auto i:G[x])
		{
            int y=i.first,w=i.second;
            if(d[y]>d[x]+w)
			{
                d[y]=d[x]+w;
                if(!vis[y])q.push({d[y],y}),vis[y]=1;
            }
        }
    }   
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,x,y,w;i<=m;i++)
	{
        scanf("%d%d%d",&x,&y,&w);
        G[x].emplace_back(PII(y,w));
        G[y].emplace_back(PII(x,w));
    }
    spfa();
    memset(sum,0,sizeof(sum));
    for(int x=1;x<=n;x++)
	{
        for(auto i:G[x])
		{
            int y=i.first,w=i.second;
            if(d[x]+w==d[y])sum[y]++;
        }
    }
    LL ans=1;
    for(int i=2;i<=n;i++)ans=ans*sum[i]%P;
    printf("%lld",ans);
    return 0;
}