bzoj 5056: OI游戏

.

题意：在一个无向连通图中，有几种生成树使1到每个点的最短路的长度不变。
题解：先求出1到每个点的最短路，在看看每个点可以从哪些边走过来依然是最短路。每个点都选一条，那么答案就是每个点的这种边的乘积了。
代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,mp[60][60],dis[60][60],mod=1000000007;
long long ans=1;

int main()
{
    memset(dis,63,sizeof(dis));
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        char s[60];
        scanf("%s",s);
        for(int j=0;j<n;j++)
        {
            mp[i][j]=s[j]-'0';
            if(mp[i][j]||i==j)
            dis[i][j]=mp[i][j];
        }
    }
    for(int k=0;k<n;k++)
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    for(int i=1;i<n;i++)
    {
        int hh=0;
        for(int j=0;j<n;j++)
        if(mp[i][j]&&dis[0][i]==dis[0][j]+mp[i][j])
        hh++;
        ans=ans*hh%mod;
    }
    printf("%lld",ans);
}