比赛 10101115 评测结果 WEWWEEEEEE
题目名称 最小密度路径 最终得分 0
用户昵称 苏轼 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-11-15 10:55:11
显示代码纯文本
#include <cstdio>

const int MAXN=55;
const double oo=1e18;

struct Node
{
	int v,w;
	Node *next;
	Node(int a,int b,Node *c):v(a),w(b),next(c){}
}*adj[MAXN];

void add(int a,int b,int w)
{
	adj[a]=new Node(b,w,adj[a]);
}

double re[MAXN][MAXN];
int now,N,M,Q;
bool vis[MAXN];
void dfs(int u,int tw,int tot)
{
	if (re[now][u]>double(tw)/tot)
		re[now][u]=double(tw)/tot;
	for(Node *p=adj[u];p;p=p->next)
		dfs(p->v,tw+p->w,tot+1);
}

int main()
{
	freopen("path.in","r",stdin);
	freopen("path.out","w",stdout);
	scanf("%d%d",&N,&M);
	for(int i=0;i<M;i++)
	{
		int a,b,w;
		scanf("%d%d%d",&a,&b,&w);
		add(a,b,w);
	}
	for(int i=1;i<=N;i++)
		for(int j=1;j<=N;j++)
			re[i][j]=oo;
	scanf("%d",&Q);
	while(Q--)
	{
		int X,Y;
		scanf("%d%d",&X,&Y);
		if (!vis[X])
		{
			now=X;
			dfs(X,0,0);
			vis[X]=true;
		}
		printf("%lf\n",re[X][Y]);
	}
	return 0;
}