rt，long long的版本第五个测试点错得离谱，非精度问题，输出500万

long long版本：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1e3;
struct pai{
	int s,e;
	long long d;
}a[2*N];
struct rec{
	int e,nex;
	long long d;
}z[2*N];
int en,fi[N];
void add(int s,int e,long long d){
	z[++en].e=e;
	z[en].nex=fi[s];
	z[en].d=d;
	fi[s]=en;
}
int n,m;
long long val[N],d[N];
void init(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i) scanf("%lld",&val[i]);
	for (int i=1;i<=m;++i){
		scanf("%d%d%lld",&a[i].s,&a[i].e,&a[i].d);
	}
}
int cnt[N];
bool inq[N];
queue<int>q;
bool spfa(int u){
	d[u]=0;inq[u]=true;
	q.push(u);
	while (q.empty()==false){
		u=q.front();
		q.pop();inq[u]=false;
		for (int i=fi[u];i!=0;i=z[i].nex){
			if (d[z[i].e]<d[u]+z[i].d){
				d[z[i].e]=d[u]+z[i].d;
				cnt[z[i].e]=cnt[u]+1;
				if (cnt[z[i].e]>n+1) return true;
				if (inq[z[i].e]==false){
					inq[z[i].e]=true;
					q.push(z[i].e);
				}
			}
		}
	}
	return false;	
}
bool check(long long tim){
	en=0;
	printf("mid=%lld\n",tim);
	for (int i=1;i<=n+1;++i) fi[i]=0;
	for (int i=1;i<=m;++i){
		add(a[i].s,a[i].e,1000000*val[a[i].s]-tim*a[i].d);
//		printf("s=%d e=%d val=%lld\n",a[i].s,a[i].e,val[a[i].s]-tim*a[i].d);
	}
	printf("\n");
	for (int i=1;i<=n;++i){
		add(n+1,i,0);
	}
	for (int i=1;i<=n+1;++i){
		cnt[i]=0;d[i]=-1e18;inq[i]=false;
	}
	while (q.empty()==false) q.pop();
	return spfa(n+1);
}
void work(long long l,long long r){
	double v;
	long long mid;
	while (l<r){
		mid=(l+r+1)>>1;
		if (check(mid)==true) l=mid;
		else r=mid-1;
	}
	v=1.0*l/1000000;
	printf("%.2lf",v);
}
int main(){
	init();
	work(0,1e18);
	return 0;
}

double 版本：

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+1e3;
struct pai{
	int s,e;
	double d;
}a[2*N];
struct rec{
	int e,nex;
	double d;
}z[2*N];
int en,fi[N];
void add(int s,int e,double d){
	z[++en].e=e;
	z[en].nex=fi[s];
	z[en].d=d;
	fi[s]=en;
}
int n,m;
double val[N],d[N];
void init(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i) scanf("%lf",&val[i]);
	for (int i=1;i<=m;++i){
		scanf("%d%d%lf",&a[i].s,&a[i].e,&a[i].d);
	}
}
int cnt[N];
bool inq[N];
queue<int>q;
bool spfa(int u){
	d[u]=0;inq[u]=true;
	q.push(u);
	while (q.empty()==false){
		u=q.front();
		q.pop();inq[u]=false;
		for (int i=fi[u];i!=0;i=z[i].nex){
			if (d[z[i].e]<d[u]+z[i].d){
				d[z[i].e]=d[u]+z[i].d;
				cnt[z[i].e]=cnt[u]+1;
				if (cnt[z[i].e]>n+1) return true;
				if (inq[z[i].e]==false){
					inq[z[i].e]=true;
					q.push(z[i].e);
				}
			}
		}
	}
	return false;	
}
bool check(double tim){
	en=0;
//	printf("mid=%.2lf\n",tim);
	for (int i=1;i<=n+1;++i) fi[i]=0;
	for (int i=1;i<=m;++i){
		add(a[i].s,a[i].e,val[a[i].s]-tim*a[i].d);
//		printf("s=%d e=%d val=%lld\n",a[i].s,a[i].e,val[a[i].s]-tim*a[i].d);
	}
//	printf("\n");
	for (int i=1;i<=n;++i){
		add(n+1,i,0);
	}
	for (int i=1;i<=n+1;++i){
		cnt[i]=0;d[i]=-1e18;inq[i]=false;
	}
	while (q.empty()==false) q.pop();
	return spfa(n+1);
}
void work(long long l,long long r){
	double v;
	long long mid;
	while (l<r){
		mid=(l+r+1)>>1;
		v=1.0*mid/1000000;
		if (check(v)==true) l=mid;
		else r=mid-1;
	}
	v=1.0*l/1000000;
	printf("%.2lf",v);
}
int main(){
	init();
	work(0,1e18);
	return 0;
}