Problem Description

XX星球有很多城市，每个城市之间有一条或多条飞行通道，但是并不是所有的路都是很安全的，每一条路有一个安全系数s,s是在 0 和 1 间的实数(包括0，1)，一条从u 到 v 的通道P 的安全度为Safe(P) = s(e1)*s(e2)…*s(ek) e1,e2,ek是P 上的边 ，现在8600 想出去旅游，面对这这么多的路，他想找一条最安全的路。但是8600 的数学不好，想请你帮忙 ^_^

 

Input

输入包括多个测试实例，每个实例包括：
第一行：n。n表示城市的个数n<=1000;
接着是一个n*n的矩阵表示两个城市之间的安全系数，(0可以理解为那两个城市之间没有直接的通道)
接着是Q个8600要旅游的路线,每行有两个数字，表示8600所在的城市和要去的城市

 

Output

如果86无法达到他的目的地，输出"What a pity!",
其他的输出这两个城市之间的最安全道路的安全系数,保留三位小数。

 

Sample Input

 

Sample Output

 

#include<iostream>

#include<algorithm>

#include<cstdlib>

#include<sstream>

#include<cstring>

#include<cstdio>

#include<string>

#include<deque>

#include<stack>

#include<cmath>

#include<queue>

#include<set>

#include<map>

#define INF 0x3f3f3f3f

#define MM(x) memset(x,0,sizeof(x))

using namespace std;

typedef long long LL;

typedef pair<int,double> pid;

const int N=900;

double E[N][N];

double d[N];

int num[N];

void init()

{

	MM(d);

	MM(E);

	MM(num);

}

int main(void)

{

	int n,q,i,j,k;

	double val;

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

	{

		init();

		for (i=0; i<n; i++)

		{

			for (j=0; j<n; j++)

			{

				scanf("%lf",&val);

				if(val==0)

					continue;

				E[i][j]=val;

				E[j][i]=val;

			}

		}

		scanf("%d",&q);

		int s,t;

		for (int w=0; w<q; w++)

		{

			scanf("%d%d",&s,&t);

			s--;t--;

			MM(d);

			priority_queue<pid>Q;

			d[s]=E[s][s];

			Q.push(pair<double,int>(d[s],s));

			while (!Q.empty())

			{

				int now=Q.top().second;

				Q.pop();

				for (i=0; i<n; i++)

				{

					if(E[now][i]==0||i==now)

						continue;

					if(d[i]<d[now]*E[now][i])

					{

						d[i]=d[now]*E[now][i];

						Q.push(pair<double,int>(d[i],i));

					}

				}

			}

			d[t]?printf("%.3lf\n",d[t]):puts("What a pity!");

		}

	}

	return 0;

}