记录编号	134317	评测结果	AWAAWWWW
题目名称	最小密度路径	最终得分	37
用户昵称	MINE·MINE	是否通过	未通过
代码语言	C++	运行时间	0.161 s
提交时间	2014-10-29 21:04:22	内存使用	0.59 MiB

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int Max=0x3f3f3f3f;
int n,m;
int q;
struct Line
{
	int next;
	int to;
	int data;
}net[1005]={0};
int head[55]={0},tot=0;
inline void dispose(int,int,int);
/*============================================================================*/
void Spfa(int);
queue<int> qpoint,qnum;
int dis[55][1005]={0};
double ans[55][55]={0};;
bool flag[55][1005]={0};
/*============================================================================*/
int main()
{
    freopen("path.in","r",stdin);
	freopen("path.out","w",stdout);
	scanf("%d%d",&n,&m);
	int i,j,x,y,z;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		ans[i][j]=Max;
	}
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		dispose(x,y,z);
	}
	for(i=1;i<=n;i++)
	Spfa(i);
	/*for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		cout<<ans[i][j]<<' ';
		cout<<endl;
	}*/
	scanf("%d",&q);
	for(i=1;i<=q;i++)
	{
		scanf("%d%d",&x,&y);
		if(ans[x][y]!=Max)
		printf("%.3lf\n",ans[x][y]);
		else
		printf("OMG!\n");
	}
	fclose(stdin);	fclose(stdout);
	return 0;
}
/*============================================================================*/
inline void Spfa(int x)
{
	memset(dis,0x3f3f3f3f,sizeof(dis));
	memset(flag,0,sizeof(flag));
	qpoint.push(x);	qnum.push(0);
	flag[x][0]=1;
	dis[x][0]=0;
	int i,j,tpoint,kpoint,knum;
	while(!qpoint.empty())
	{
		kpoint=qpoint.front();	knum=qnum.front();
		qpoint.pop();	qnum.pop();
		for(i=head[kpoint];i!=0;i=net[i].next)
		{
			tpoint=net[i].to;
			if(dis[tpoint][knum+1]>dis[kpoint][knum]+net[i].data)
			{
				dis[tpoint][knum+1]=dis[kpoint][knum]+net[i].data;
				if(!flag[tpoint][knum+1])
				{
					flag[tpoint][knum+1]=1;
					qpoint.push(tpoint);
					qnum.push(knum+1);
				}
			}
		}
		flag[kpoint][knum]=0;
	}
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			if(dis[i][j]!=Max)
			{
				if(ans[x][i]>(double)dis[i][j]/(double)j)
				ans[x][i]=(double)dis[i][j]/(double)j;
			}
		}
	}
	ans[x][x]=0;
	return ;
}
/*============================================================================*/
inline void dispose(int x,int y,int z)
{
	tot++;
	net[tot].to=y;
	net[tot].data=z;
	net[tot].next=head[x];
	head[x]=tot;
	return ;
}