思路

正权保证每个非根顶点选择任意最短路前驱不会成环，方案数为前驱边数乘积；最短路树不等于MST，断图无方案，模2^31-1。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,m;cin>>n>>m;vector<vector<pair<int,int>>>g(n);vector<tuple<int,int,int>>edges;for(int i=0;i<m;i++){int u,v,w;cin>>u>>v>>w;--u;--v;g[u].push_back({v,w});g[v].push_back({u,w});edges.push_back({u,v,w});}const int INF=1000000000;vector<int>d(n,INF),count(n);priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;d[0]=0;q.push({0,0});while(!q.empty()){auto p=q.top();q.pop();int v=p.second;if(p.first!=d[v])continue;for(auto e:g[v])if(d[e.first]>d[v]+e.second){d[e.first]=d[v]+e.second;q.push({d[e.first],e.first});}}for(auto e:edges){int u,v,w;tie(u,v,w)=e;if(d[u]+w==d[v])count[v]++;if(d[v]+w==d[u])count[u]++;}long long ans=1;for(int v=1;v<n;v++){if(d[v]==INF){cout<<0<<'\n';return 0;}ans=ans*count[v]%2147483647;}cout<<ans<<'\n';}