记录编号	21862	评测结果	AAAAAAAAWW
题目名称	最小密度路径	最终得分	80
用户昵称	wangwangdog	是否通过	未通过
代码语言	C++	运行时间	2.170 s
提交时间	2010-11-15 17:23:57	内存使用	1.28 MiB

#include<stdio.h>
#include<math.h>
long long n,m,map[51][51],i,j,k,nn,a,b,l,d[51][51][51],bian;
 
FILE *fin,*fout;
int main()
{
	fin=fopen("path.in","rb");
	fout=fopen("path.out","wb");
	fscanf(fin,"%lld%lld\n",&n,&m);
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			map[i][j]=2111111111;
	for(i=1;i<=m;i++)
	{
		fscanf(fin,"%lld%lld%lld\n",&a,&b,&l);
		if(map[a][b]==2100000000)map[a][b]=l;
		else if(l<map[a][b])map[a][b]=l;
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			for(k=1;k<=n;k++)
				d[i][j][k]=2111111111;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			d[i][j][1]=map[i][j];
			
		}
	
	for(bian=2;bian<=n;bian++)
	{
		for(k=1;k<=n;k++)
			for(i=1;i<=n;i++)
				for(j=1;j<=n;j++)
				{
					
					if(d[i][k][bian-1]+d[k][j][1]<d[i][j][bian])
					{d[i][j][bian]=d[i][k][bian-1]+d[k][j][1];}
					
				}
	}
	fscanf(fin,"%lld\n",&nn);
	for(i=1;i<=nn;i++)
	{
		fscanf(fin,"%lld%lld\n",&a,&b);
		double min=2111111111;
		for(j=1;j<=n;j++)
		{
			if(d[a][b][j]!=2111111111)
			{
				double rr=d[a][b][j];
				if(rr/j<min)min=rr/j;
			}
		}
		if(min>=2099999999)fprintf(fout,"OMG!\n");
		
		else fprintf(fout,"%0.3lf\n",min);
	}
	fclose(fin);
	fclose(fout);
	return 0;
}