Road(floyd+思维)

# Road

题意

连通图，删去尽可能多的路，使得每个城市到第0号城市的最短路长度不变，求可能的方案数量。

用floyd先求出每个城市之间的最短路，然后对每条0i城市的最短路，判断0j城市的距离加上i到j的原始距离是否还和最短路相等，相等的话，在j城市上的最短路径+1。最后将他们乘起来。

看！代码

#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=350;
const long long MOD=1e9+7;
int dist[maxn],g[maxn][maxn],f[maxn][maxn],N;
long long road[maxn];
long long floyd()
{
    long long ans=1;
    memset(road,0,sizeof(road));

    for (int k=0;k<N;k++)
        for (int i=0;i<N;i++)
            for (int j=0;j<N;j++)
                if (i!=k&&i!=j&&j!=k)
                    g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
    g[0][0]=0;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        if(i!=j&&g[0][i]+f[i][j]==g[0][j])
    {
        road[j]++;
    }
    for(int i=1;i<N;i++)
        if(road[i])
            ans=(ans*road[i])%MOD;
    return ans;

int main()
{
    while(scanf("%d",&N)!=EOF)
    {
        memset(g,INF,sizeof(g));
        string s;
        for(int i=0;i<N;i++)
        {
            cin>>s;
            for(int j=0;j<s.size();j++)
            {
                if(s[j]=='0')
                    f[i][j]=g[i][j]=INF;
                else
                	f[i][j]=g[i][j]=s[j]-'0';
            }
        }
        printf("%lld\n",floyd());
    }
    return 0;
}