记录编号	22110	评测结果	AWAWWWTTTT
题目名称	501.最小密度路径	最终得分	20
用户昵称	Pom	是否通过	未通过
代码语言	C++	运行时间	4.300 s
提交时间	2010-11-17 11:27:29	内存使用	28.03 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>

using namespace std;

const int MAXN=60;
const int MAXM=1011;
const double oo=1000000000;

int i,j,k,Q,n,m,p1,p2;
double a[MAXN][MAXN][MAXM],r,ans;

void init()
{
	freopen("path.in","r",stdin);
	freopen("path.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)
		for (j=1;j<=n;j++)
			for (k=1;k<=m;k++)
			a[i][j][k]=oo;
	for (Q=1;Q<=m;Q++)
	{
		scanf("%d%d%lf",&i,&j,&r);
		if (r<a[i][j][1]) a[i][j][1]=r;
	}
}

void solve()
{
	for (k=1;k<=n;k++)
		for (i=1;i<=n;i++)
			for (j=1;j<=n;j++)
				for (p1=1;p1<m;p1++)
					for (p2=1;p2<=m-p1;p2++)
						if (a[i][k][p1]+a[k][j][p2]<a[i][j][p1+p2]) a[i][j][p1+p2]=a[i][k][p1]+a[k][j][p2];
	scanf("%d",&Q);
	for (;Q;Q--)
	{
		ans=oo;
		scanf("%d%d",&i,&j);
		for (k=1;k<=m;k++)
			if (ans>a[i][j][k]/k) ans=a[i][j][k]/k;
		if (ans<=10000000)
			printf("%0.3lf\n",ans);
		else printf("OMG!\n");
	}
}

int main()
{
	init();
	solve();
	return 0;
}