题意
有一个n个节点的无向图，结点编号从0-n-1，每条边的长度时1to9的一个正整数。现在要删除一些边(或者不删)，使得到的新图满足下面两个要求。
1.
新图是一颗树有n-1条边
2.
对于每个结点v（0ton-1）从0到v的距离要等于原图上从0到v的最短路
现在计算有多少种不同的图满足上面两个条件
分析
统计每个点可以到达最短路的入度值，然后相乘。这个题因为spfa写错了调了老久···
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <queue> 6 7 using namespace std; 8 const int INF=2147483600; 9 const int maxn=55; 10 const int MOD=1000000007; 11 int n; 12 char g[maxn][maxn]; 13 int G[maxn][maxn]; 14 int d[maxn],vis[maxn]; 15 long long in[maxn]; 16 long long ans; 17 void spfa(){ 18 memset(vis,0,sizeof(vis)); 19 for(int i=0;i<=n;i++)d[i]=INF; 20 queue<int>q; 21 q.push(0);vis[0]=1; 22 d[0]=0; 23 while(!q.empty()){ 24 int u=q.front();q.pop(); 25 vis[u]=0; 26 for(int i=0;i<n;i++){ 27 if(G[u][i]){ 28 if(d[i]>=d[u]+G[u][i]){ 29 d[i]=d[u]+G[u][i]; 30 if(!vis[i]){ 31 vis[i]=1; 32 q.push(i); 33 } 34 } 35 } 36 } 37 } 38 return; 39 } 40 int main(){ 41 while(scanf("%d",&n)!=EOF){ 42 memset(G,0,sizeof(G)); 43 for(int i=0;i<n;i++){ 44 for(int j=0;j<n;j++){ 45 scanf(" %c",&g[i][j]); 46 } 47 } 48 for(int i=0;i<n;i++){ 49 for(int j=0;j<n;j++){ 50 G[i][j]=g[i][j]-'0'; 51 } 52 } 53 spfa(); 54 memset(in,0,sizeof(in)); 55 for(int i=0;i<n;i++){ 56 for(int j=0;j<n;j++){ 57 if(i!=j){ 58 if(G[i][j]&&d[j]==d[i]+G[i][j]){ 59 in[j]++; 60 } 61 } 62 } 63 } 64 ans=1; 65 for(int i=0;i<n;i++){ 66 if(in[i]) 67 ans=(ans%MOD*in[i]%MOD)%MOD; 68 } 69 printf("%lld ",ans); 70 } 71 return 0; 72 }