题目大意:给你一个图,要把它删成一棵树,并且使得0这个结点从树上到达任意结点的距离和原图中的最短路径相等
分析:我们对于某一个点来说,只需要知道有多少条和到这个点最短路的路径,乘起来就可以
注意个数是一个乘积的形式,应该用一种递推的方式去求;
#include <bits/stdc++.h>
using namespace std;
int g[55][55];
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
typedef long long ll;
struct node
{
int top,d;
node(int t,int d):top(t),d(d){}
bool operator<(const node&oth)const
{
return d>oth.d;
}
};
int d[100];
ll cnt[100];
int n;
void dijstra(){
memset(d,inf,sizeof(d));
priority_queue<node>pq;
pq.push(node(1,0));
d[1]=0;
while(!pq.empty()){
node temp=pq.top();
pq.pop();
int u=temp.top;
int c=temp.d;
for(int i=1;i<=n;i++)
{
if(g[u][i]!=0)
{
int v=i;
int w=g[u][i];
if(d[v]>d[u]+w)
{
d[v]=d[u]+w;
pq.push(node(v,d[v]));
}
}
}
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%1d",&g[i][j]);
}
}
dijstra();
ll ans=1;
for(int i=1;i<=n;i++){
cnt[i]=0;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(g[i][j]&&d[i]==(d[j]+g[i][j])){
cnt[i]++;
}
}
}
for(int i=2;i<=n;i++){
ans*=cnt[i];
ans%=mod;
}
printf("%lld\n",ans);
}
return 0;
}