比赛 |
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;
}