usaco 地震 && 奶牛观光

Usaco 地震:

我用了种比较傻的：

time[i]表示该点被更新了几次，如果大于 n 显然存在负权环

图图大神还说：SPFA的使用十分灵活，经常配合动规使用，所以往往队列里的初始状态是不唯一的。

代码如下:

 #include<cstring>

 #include<algorithm>

 #include<cstdio>

 #include<string>

 #include<iostream>

 #include<queue>

 #define INF 999999999

 #define N 5011

 const double E=1e- ;

 using namespace std;

 queue <int> q;

 int n,P;

 int T,last[N],next[N],s[N];

 double sum[N],t[N],l,r,mid,ans;

 bool check(){

     int time[N]; memset(time,,sizeof(time));

     double d[N]; for(int i=;i<=n;i++) d[i]=INF;

     bool in[N]; memset(in,,sizeof(in));

     time[]=in[]=; d[]=;

     while(!q.empty()) q.pop();

     for(q.push();!q.empty();q.pop()){

         int now=q.front();

         for(int i=last[now];i;i=next[i]){

             double w=t[i]*mid-sum[now];

             if(d[s[i]]+E>d[now]+w){

                 d[s[i]]=d[now]+w;

                 if(!in[s[i]]){

                     in[s[i]]=;

                     q.push(s[i]);

                     if(++time[s[i]]>n) return ;

                 }

             }

         }

         in[now]=;

     }

     return ;

 }

 int main(){

     scanf("%d%d",&n,&P);

     for(int i=;i<=n;i++) scanf("%lf",&sum[i]);

     for(int i=;i<=P;i++){

       int x,y;

       double v;

       scanf("%d%d%lf",&x,&y,&v);

       next[++T]=last[x]; last[x]=T; s[T]=y; t[T]=v;

     }

     l=E,r=;

     while(r-l>=E){

         mid=(l+r)/;

         if(check()){

             ans=mid;

             l=mid+E;

         } else r=mid-E;

     }

     printf("%.2lf",ans);

 }