题目大意:

题解:

首先我们容易发现最优的路线一定只经过一个环。

所以我们可以把点权合并到边权上.

然后就转化为了一个01分数规划问题

求解即可

#include 
    
     #include 
     
      #include 
      
       using namespace std;typedef long long ll;inline void read(int &x){    x=0;char ch;bool flag = false;    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;}const int maxn = 1024;const int maxm = 5010;const double eps = 1e-6;inline int dcmp(const double &x){    if(x < eps && x > -eps) return 0;    return x > 0 ? 1 : -1;}struct Edge{    int to,next,d;    double dis;}G[maxm<<1];int head[maxn],cnt;void add(int u,int v,int d){    G[++cnt].to = v;    G[cnt].next = head[u];    head[u] = cnt;    G[cnt].d = d;}double dis[maxn];bool inq[maxn];#define v G[i].tobool dfs(int u){    inq[u] = true;    for(int i = head[u];i;i=G[i].next){        if(dis[v] > dis[u] + G[i].dis){            dis[v] = dis[u] + G[i].dis;            if(inq[v]) return true;            if(dfs(v)) return true;        }    }inq[u] = false;    return false;}#undef vint w[maxn],n,m;inline bool check(double mid){    memset(inq,0,sizeof inq);    memset(dis,0,sizeof dis);    for(int i=1;i<=cnt;++i)        G[i].dis = mid*G[i].d - w[G[i].to];    for(int i=1;i<=n;++i)         if(dfs(i)) return true;    return false;}int main(){    read(n);read(m);    for(int i=1;i<=n;++i) read(w[i]);    for(int i=1,u,v,d;i<=m;++i){        read(u);read(v);read(d);        add(u,v,d);//add(v,u,d);    }    double l = .0,r = 1e9;    while((r-l) > eps){        double mid = (l+r)/2;        if(check(mid)) l = mid;        else r = mid;    }printf("%.2lf\n",l);    getchar();getchar();    return 0;}