记录编号	252761	评测结果	AAAAAAAA
题目名称	最小密度路径	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.059 s
提交时间	2016-04-20 21:29:58	内存使用	11.86 MiB

#include<cstdio>
#include<algorithm>
//#include"debug.h"
using namespace std;

const int maxl=1000010;
const int maxn=99999999;
struct edge{
	int f,t,l;
}w[2010];
int n,m,q,head[110],tail[110],next[2010],i,j,k;
double ans[110][110];

int heap[maxl],hash[maxl],top,dist[maxl];
//dist[i+k*n]表示到i点，共经过k条边时的最短路 
bool cmp(int x,int y){
	return dist[heap[x]]<dist[heap[y]];
}
void swap(int &x,int &y){
	int a=heap[x];
	heap[x]=heap[y];heap[y]=a;
	hash[heap[x]]=x;hash[heap[y]]=y;
	x=y;
}
void insert(int x){
	int fa,son=++top;
	heap[son]=x;hash[x]=son;
	while (son>1){
		fa=son/2;
		if (cmp(fa,son)) return;
		swap(son,fa);
	}
}
void pop(){
	int fa=1,son;
	hash[heap[1]]=0;
	heap[1]=heap[top--];
	if (top==0) return;
	hash[heap[1]]=1;
	while (fa<=top){
		son=fa*2;
		if (son>top) return;
		if (son+1<=top&&cmp(son+1,son)) son++;
		if (cmp(fa,son)) return;
		swap(fa,son);
	}
}
void Maintain(int x){
	int fa,son=hash[x];
	while (son>1){
		fa=son/2;
		if (cmp(fa,son)) return;
		swap(son,fa);
	}
}
void dijsktra(int x){
	int i,j,v,c;
	for (i=1;i<=n*(n+1);i++) dist[i]=maxn;
	dist[x]=0;
	insert(x);
	while (top>0){
		v=heap[1];pop();
		if (v>(m+1)*n) continue;
		c=((v-1)/n)*n;
		j=v-c;
		for (i=head[j];i!=0;i=next[i])
		if (dist[w[i].t+c+n]>dist[v]+w[i].l){
			dist[w[i].t+c+n]=dist[v]+w[i].l;
			if (hash[w[i].t+c+n]==0) insert(w[i].t+c+n);
				else Maintain(w[i].t+c+n);
		}
	}
}

int main()
{
	freopen("path.in","r",stdin);
	freopen("path.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;i++){
		scanf("%d%d%d",&w[i].f,&w[i].t,&w[i].l);
		if (head[w[i].f]==0) head[w[i].f]=tail[w[i].f]=i;
			else tail[w[i].f]=next[tail[w[i].f]]=i;
	}
	
	for (i=1;i<=n;i++)
	for (j=1;j<=n;j++)
	ans[i][j]=maxn;
	for (i=1;i<=n;i++){
		dijsktra(i);
		for (j=1;j<=n;j++)
		for (k=0;k<=n;k++)
		if (dist[j+k*n]!=maxn)
			ans[i][j]=min(ans[i][j],(double)dist[j+k*n]/k);
	}
	
	scanf("%d",&q);
	for (;q>0;q--){
		scanf("%d%d",&i,&j);
		if (ans[i][j]>100000) printf("OMG!\n");
			else printf("%.3lf\n",ans[i][j]);
	}
	return 0;
}