题目名称	501. 最小密度路径
输入输出	`path.in/out`
难度等级	★★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	8
题目来源	cqw 于2010-11-14加入
开放分组	全部用户
提交状态
分类标签
	分享题解

通过：75，提交：309，通过率：24.27%
yedu	100	0.024 s	0.36 MiB	C++
yedu	100	0.030 s	0.24 MiB	C++
Bennettz	100	0.037 s	0.24 MiB	C++
Regnig Etalsnart	100	0.044 s	0.20 MiB	C++
Regnig Etalsnart	100	0.048 s	0.20 MiB	C++
hzoi55223	100	0.051 s	0.37 MiB	C++
JSX	100	0.052 s	0.96 MiB	C++
FoolMike	100	0.059 s	11.86 MiB	C++
cstdio	100	0.060 s	0.97 MiB	C++
梦那边的美好ET	100	0.061 s	1.18 MiB	C++

本题关联比赛
10101115

关于最小密度路径的近10条评论(全部评论)
emmm 讲道理无环枚举n-1条边不就可以了么原来全是环qwq还搞得我数组越界了虽然有环但枚举到n就可以了。。。 CSU_Turkey 2017-10-21 21:13 10楼
spfaGG的很惨啊 CSU_Turkey 2017-10-21 20:20 9楼
考试的时候爆搜0分qwq CSU_Turkey 2017-10-21 19:56 8楼
只加n条边就行了，加m条边就会WA FoolMike 2016-04-20 21:30 7楼
重边真是无语。。 devil 2015-07-19 11:07 6楼
尼玛了……原来这么简单 MINE·MINE 2014-10-29 21:03 5楼
、、、、、无环图、、乌龙猹 2014-10-29 17:24 4楼
顿时沙茶= = dist[i][k]+dist[j][k]<dist[i][j] QAQ HouJikan 2014-09-18 16:03 3楼
除除除除除除除除除除除除了了了了了了了了了了了了 111111111111111111111 333333333333333333333 444444444444444444444 组数据其他均没没有有环环环环环环环环环环环环环环环环赵赵赵 2014-04-23 16:59 2楼
第二组数据有环：9->2->1->4->10 认为最长路可能有n条边就能过……虽然这是错的 cstdio 2014-04-22 21:14 1楼

501. 最小密度路径

★★ 输入文件：path.in 输出文件：path.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

这次的任务很简单，给出了一张有N个点M条边的加权有向无环图，接下来有Q个询问，每个询问包括2个节点X和Y，要求算出从X到Y的一条路径，使得密度最小（密度的定义为，路径上边的权值和除以边的数量）。

【输入格式】

第一行包括2个整数N和M。

以下M行，每行三个数字A、B、W，表示从A到B有一条权值为W的有向边。

再下一行有一个整数Q。

以下Q行，每行一个询问X和Y，如题意所诉。

【输出格式】

对于每个询问输出一行，表示该询问的最小密度路径的密度（保留3位小数），如果不存在这么一条路径输出“OMG!”（不含引号）。

【输入样例】

【输出样例】

5.000
5.500

【数据范围与约定】

对于60%的数据，有1 ≤ N ≤ 10，1 ≤ M ≤ 100，1 ≤ W≤ 1000，1 ≤ Q ≤ 1000；

对于100%的数据，有1 ≤ N ≤ 50，1 ≤ M ≤ 1000，1 ≤ W ≤ 100000，1 ≤ Q ≤ 100000。