因为D[i]表示i号节点到1号节点的最短路径，所以可以先以1为源点跑一边SPFA，预处理出每个点到1号节点的最短路。之后开始考虑所谓的“最短路径生成树”，在这棵生成树中有以下性质：当fa[i]==node时，必满足dist[node]+w(node,i)=dist[i]，但是dist[node]+w(node,i)==dist[i]时，node不一定是i的父节点，因为图的最短路可能有多条。因此我们记录mul[i]为i的前驱个数，也就是所有满足dist[k]+w(k,i)==dist[i]的点的个数。根据乘法原理累计相乘即可求出答案。
常见疑问：
Q1：为什么这样构造出来一定是一棵树？？？
A1：因为对于每一棵生成树，除1号节点外，都有一个唯一的前驱，我们假想他们之间连了一条边，则连了(n-1)条边，并且保证联通性，根据树的定义，可以保证这是一棵树。
Q2：为什么可以不排序？？？网上大神排序出于什么目的？？？
A2：因为边权均为正，所以比较dist值较大的节点只能从dist值较小的节点走过来，因此对i号节点统计时我们是用不到dist值比i大的节点的，因此使用O(NlogN)的时间按每个节点dist值进行排序，即可省去一半的时间。注意，不排序对正确性没有影响。
Q3：为什么不用伟大的Dijkstra堆优化而使用已经死了的SPFA？？？
A3：LQX学长调他的堆优化调了一个下午。
参考代码如下：
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<queue> 5 #define int long long 6 #define mod 2147483647 7 #define N 1005 8 #define M 1000005 9 #define INF 110412365 10 using namespace std; 11 struct node 12 { 13 int num,dist; 14 }point[N]; 15 int n,m,v[M],w[M],head[M],nxt[M],cnt,x,y,z,mul[N]; 16 bool vis[N]; 17 void add(int a,int b,int c) 18 { 19 v[++cnt]=b; 20 w[cnt]=c; 21 nxt[cnt]=head[a]; 22 head[a]=cnt; 23 } 24 int read() 25 { 26 int x=0,f=1;char ch=getchar(); 27 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 28 while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} 29 return x*f; 30 } 31 void spfa(int s) 32 { 33 for(int i=2;i<=n;i++)point[i].dist=INF; 34 queue<int>q; 35 q.push(s); 36 vis[s]=1; 37 while(!q.empty()) 38 { 39 int c=q.front(); 40 q.pop(); 41 vis[c]=0; 42 for(int i=head[c];i;i=nxt[i]) 43 { 44 int y=v[i]; 45 if(point[y].dist>point[c].dist+w[i]) 46 { 47 point[y].dist=point[c].dist+w[i]; 48 if(!vis[y]) 49 { 50 q.push(y); 51 vis[y]=1; 52 } 53 } 54 } 55 } 56 } 57 bool cmp(node a,node b) 58 { 59 return a.dist<b.dist; 60 } 61 signed main() 62 { 63 n=read();m=read(); 64 for(int i=1;i<=m;i++) 65 { 66 x=read();y=read();z=read(); 67 add(x,y,z);add(y,x,z); 68 } 69 spfa(1); 70 for(int i=1;i<=n;i++) 71 { 72 for(int j=head[i];j;j=nxt[j]) 73 { 74 if(point[i].dist+w[j]==point[v[j]].dist)mul[v[j]]++; 75 } 76 } 77 int ans=1; 78 for(int i=2;i<=n;i++)ans*=mul[i],ans%=mod; 79 cout<<ans<<endl; 80 return 0; 81 }