易错点：
- 二分时，l,r,mid的类型都要设为double.
- 0/1规划问题在该类图上可转化为乘积的形式并使用spfa判断当前解是否合理.
- 注意区分i和i所代表的点a[i].
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
#define eps 1e-3
using namespace std;
const int MAXN=2e3,MAXM=1e4;
struct Edge{
int from,to,nxt;
double w;
}e[MAXM];
int head[MAXN],edgeCnt=1;
void addEdge(int u,int v,double w){
e[++edgeCnt].from=u;
e[edgeCnt].to=v;
e[edgeCnt].w=w;
e[edgeCnt].nxt=head[u];
head[u]=edgeCnt;
}
double dis[MAXN];
int n,enterNum[MAXN];
bool inQueue[MAXN];
bool spfa(){
memset(dis,0x3f,sizeof(dis));
memset(enterNum,0,sizeof(enterNum));
queue<int> q;
for(int i=1;i<=n;i++){
q.push(i);
inQueue[i]=1;
}
while(!q.empty()){
if(dis[q.front()]>dis[q.back()])swap(q.front(),q.back());
int nowPoint=q.front();q.pop();
inQueue[nowPoint]=0;
for(int i=head[nowPoint];i;i=e[i].nxt){
int nowV=e[i].to;
if(dis[nowV]>dis[nowPoint]+e[i].w){
dis[nowV]=dis[nowPoint]+e[i].w;
enterNum[nowV]++;
if(enterNum[nowV]>n)return 1;
if(inQueue[nowV])continue;
q.push(nowV);
inQueue[nowV]=1;
}
}
}
return 0;
}
int a[MAXM],b[MAXM],t[MAXM],f[MAXN];
int m;
bool judge(double nowValue){
memset(head,0,sizeof(head));
edgeCnt=1;
for(int i=1;i<=m;i++){
addEdge(a[i],b[i],nowValue*t[i]-f[a[i]]);
}
return spfa();
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&f[i]);
}
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a[i],&b[i],&t[i]);
}
double l=0,r=1e3;
while(r-l>eps){
double mid=(l+r)/2;
if(judge(mid))l=mid;
else r=mid;
}
printf("%.2f
",l);
return 0;
}