小澳最喜欢的歌曲就是《葫芦娃》。
一日表演唱歌，他尽了洪荒之力，唱响心中圣歌。
随之，小澳进入了葫芦世界。
葫芦世界有 n 个葫芦，标号为 1~ n。 n 个葫芦由 m 条藤连接， 每条藤连接了 两个葫芦， 这些藤构成了一张有向无环图。小澳爬过每条藤都会消耗一定的能量。
小澳站在 1 号葫芦上（你可以认为葫芦非常大，可以承受小澳的体重），他 想沿着藤爬到 n 号葫芦上， 其中每个葫芦只经过一次。
小澳想找到一条路径，使得消耗的能量与经过的葫芦数的比值最小。
输入格式 calabash.in
输入文件第一行两个正整数 n,m， 分别表示葫芦的个数和藤数。
接下来 m 行，每行三个正整数 u,v,w，描述一条藤，表示这条藤由 u 连向 v，
小澳爬过这条藤需要消耗 w 点能量。
输出格式 calabash.out
一行一个实数， 表示答案（ 误差不超过 10^-3）。
输入样例
4 6
1 2 1
2 4 6
1 3 2
3 4 4
2 3 3
1 4 8
输出样例
2.000
输入输出样例说明
有 4 种爬法：
1->4，消耗能量 8，经过 2 个葫芦， 比值为 8/2=4。
1->2->4， 消耗能量 1+6=7， 经过 3 个葫芦， 比值为 7/3≈2.33。
1->3->4， 消耗能量 2+4=6， 经过 3 个葫芦， 比值为 6/3=2。
1->2->3->4， 消耗能量 1+3+4=8， 经过 4 个葫芦， 比值为 8/4=2。
所以选第三种或第四种方案， 答案为 2。
二分答案
若答案经过的路径有k条边，答案为ans，边权设为ai
则
$$frac{sum_{i=1}^k a_i}{k+1}=ans$$ 将k乘过去，两边各减去k个ans得到
$$sum_{i=1}^k (a_i-ans) - ans=0$$ 判断最短路和0的大小关系进行二分ans
代码
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const double eps=1e-4;
const double inf=1e6;
struct edge {
int next;
int to;
double dis,now;
} map[500005];
int head[10005];
int num=0;
void addedge(int from,int to,double dis)
{
map[++num].next=head[from];
map[num].to=to;
map[num].dis=dis;
head[from]=num;
}
double dis[10005];
bool vis[10005];
int n,m;
bool spfa(double x)
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=num;i++){
map[i].now=map[i].dis-x;
}
for(int i=1;i<=n;i++){
dis[i]=inf;
}
dis[1]=0;
queue<int>poi;
poi.push(1);
int h,v;
vis[1]=1;
while(!poi.empty()) {
h=poi.front();
poi.pop();
vis[h]=0;
for(int i=head[h]; i; i=map[i].next) {
v=map[i].to;
if(dis[v]>dis[h]+map[i].now) {
dis[v]=dis[h]+map[i].now;
if(vis[v]==0) {
poi.push(v);
vis[v]=1;
}
}
}
}
return dis[n]-x<0;
}
int main()
{
scanf("%d %d",&n,&m);
int x,y;
double l;
double sum=0;
for(int i=1; i<=m; i++) {
scanf("%d %d %lf",&x,&y,&l);
addedge(x,y,l);
sum+=l;
}
double r=sum;l=0;
double mid;
while(r-l>eps){
mid=(l+r)/2.0;
if(spfa(mid)){
r=mid;
}
else{
l=mid;
}
}
printf("%.3lf
",l);
return 0;
}