一般推荐dfs判负环，bfs求最短路。
如果dfs判负环都T，可以尝试将bfs中queue改为stack，或者限制队列长度试试。
这里要注意的是，每次check前dist数组置为0，这里可以保证每次走的路径权值和都是负的，
减少了很多冗余路径。

(dfs判负环) 20ms+

C++ 代码

//#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
const int MAXM = 5010;
ll n,p,a,b,c,cnt[1010];
ll f[1010];
struct Edge{
    ll next,to,dat;
}edge[MAXM];
ll tot,head[1010],vis[1010];
double dist[1010];
void add(ll x,ll y,ll c){
    edge[tot].to=y;
    edge[tot].dat=c;
    edge[tot].next=head[x];
    head[x]=tot++;
}

bool dfs(int u,double mid)
{   vis[u]=true;
    for(ll i=head[u];i!=-1;i=edge[i].next){
      ll j=edge[i].to,w=edge[i].dat;
      if(dist[j]<dist[u]+f[u]-mid*w)
      { dist[j]=dist[u]+f[u]-mid*w;
        if(vis[j]||dfs(j,mid)) return true;
        vis[j]=false;

      }

    }
    vis[u]=false;
    return false;

}
bool check(double mid){
    memset(dist,0,sizeof(dist));
    memset(vis,false,sizeof(vis));
    for(ll i=1;i<=n;i++)
    if(dfs(i,mid)) return true;

    return false;
}
int main(){
    scanf("%lld%lld",&n,&p);
    memset(head,-1,sizeof(head));
    tot=0;
    for(ll i=1;i<=n;i++)
    scanf("%lld",&f[i]);
    for(ll i=0;i<p;i++)
    {   
        scanf("%lld%lld%lld",&a,&b,&c);
        add(a,b,c);
    }
    double l=0,r=1010;
    while(r-l>1e-5)
    {   double mid = (l+r)/2.0;
        if(check(mid)) l=mid;
        else r=mid;

    }    
    printf("%.2lf\n",r);
    return 0;
}