题意：

有0~n-1这几个城市是连通的，每个城市之间连接着一些道路，问有几种删除边（有可能不删除）的方案，使得这些城市还是连通的，剩下的边最少（即生成树，剩下n-1条边），对于每个城市，它们到0的最短路不变。

思路：

因为只能有n-1条边，所以对于每个点每次加边的时候只能加一条。

首先算出每个点到0的最短路，然后对于每个点找一个父节点，如果0到父节点的最短路+该点到父节点的距离=0到该点的最短路，就可以通过这个父节点来走，只多加了一条边，因为0到父节点的最短路是本来就存在的。这样遍历每个点，再把结果相乘，就是答案了。

代码：

typedef long long ll;
int g[110][110];
char a[110];
typedef pair<int,int>p;
int dis[110];
int n;
void dijkstra()
{
    fill(dis,dis+n,INF);
    dis[0]=0;
    priority_queue<p,vector<p>,greater<p> >q;
    q.push(p(0,0));
    while(!q.empty())
    {
        p temp=q.top();
        q.pop();
        int w=temp.first;
        int id=temp.second;
        if(w>dis[id])continue;
        for(int i=0;i<n;i++)
        {
            if(w+g[id][i]<dis[i])
            {
                dis[i]=w+g[id][i];
                q.push(p(dis[i],i));
            }
        }
    }
    //for(int i=0;i<n;i++)
        //printf("%d ",dis[i]);
    //printf("\n");
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<n;i++)
        {
            scanf("%s",a);
            for(int j=0;j<n;j++)
            {
                g[i][j]=a[j]-'0';
                if(i!=j&&g[i][j]==0)g[i][j]=INF;
            }
        }
        dijkstra();
        ll ans=1;
        for(int i=1;i<n;i++)
        {
            ll temp=0;
            for(int j=0;j<n;j++)
            {
                if(i!=j&&dis[j]+g[i][j]==dis[i])
                    temp++;
            }
            //printf("%lld\n",temp);
            ans=(ans*temp)%MOD;
        }
        printf("%lld\n",ans);
    }
    return 0;
}