积压很久的一道。。。一看直接spfa水过。。但是看那个safest怎么求得？松弛的时候取大。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

const double eps=1e-5;

const double pi=acos(-1.0);

const int mod=1e9+7;

const int INF=0x3f3f3f3f;

#define N 1010

double ma[N][N];

int n;

bool vis[N];

int used[N];

double dis[N];

int que[N*N];

int h,ta;

void spfa(int s,int t)

{

    h=0;

    ta=1;

    memset(dis,0,sizeof(dis));

    memset(vis,0,sizeof(vis));

    dis[s]=1;

    vis[s]=1;

    que[h]=s;

    while(h<ta)

    {

        int u=que[h++];

        vis[u]=0;

        for(int i=1;i<=n;i++)

            {

                 if(ma[u][i]==0||u==i)

                    continue;

                if(dis[i]<dis[u]*ma[u][i])

                {

                    dis[i]=dis[u]*ma[u][i];

                    if(!vis[i])

                    {

                        vis[i]=1;

                        que[ta++]=i;

                    }

                }

            }

    }

    if(dis[t]!=0)

        printf("%.3lf\n",dis[t]);

    else

        puts("What a pity!");

}

int main()

{

    while(~scanf("%d",&n))

    {

        for(int i=1;i<=n;i++)

        {

            for(int j=1;j<=n;j++)

            {

                scanf("%lf",&ma[i][j]);

            }

        }

        int m;

        scanf("%d",&m);

        for(int i=0;i<m;i++)

        {

            int a,b;

            scanf("%d%d",&a,&b);

            spfa(a,b);

        }

    }

     return 0;

 }