这要是碰上现场赛我得被搞死 从RE到TLE到WA已疯。。

这题建图没有那么直接，通过给出的不等式关系一时想不到怎么建图

所以要对题目给的条件一定程度化简，将不等式两边取对数化简得到Sa-Sb<=c的形式

要注意w取double类型

其次，这题卡时间，根据经验加剪枝：

1、出队次数>sqrt(n)则判断有负环

2、统计总的入队次数，>2n则判断有负环

一般情况下不用这个，因为不严谨

下面两个spfa都是对的，手写队列稍快一点，上面第二个剪枝效果明显

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        using namespace std; struct node { int v; double w; int next; }e[360010]; int n,m,h,head[810],inq[810],outq[810],q[50000]; double d[805]; void addedge(int a,int b,double c) { e[h].v=b; e[h].w=c; e[h].next=head[a]; head[a]=h++; } bool spfa(int s) { int iq,i,top,k; for(i=0;i<=n;i++) d[i]=1000000000; memset(inq,0,sizeof inq); memset(outq,0,sizeof outq); d[s]=0;inq[s]=1; iq=0;i=0; q[iq++]=s; while(i!=iq) { top=q[i]; inq[top]=0; outq[top]++; if(outq[top]>(int)sqrt(n*1.0)) return 0; k=head[top]; while(k>=0) { if(d[e[k].v]-e[k].w>d[top]) { d[e[k].v]=e[k].w+d[top]; if(!inq[e[k].v]) { inq[e[k].v]=1; q[iq++]=e[k].v; } } k=e[k].next; } i++; } return 1; } int spfa(int st)//邻接表 STL { for(int i=0;i<=n;i++) d[i]=100000000; memset(inq,0,sizeof inq); memset(outq,0,sizeof outq); d[st]=0;inq[st]=1; queue
       
         q; q.push(st); int cnt=1; while(!q.empty()) { int x=q.front(); q.pop(); inq[x]=0; outq[x]++; if(outq[x]>sqrt(n*1.0)+10) return 0; for(int i=head[x];i!=-1;i=e[i].next) { if(d[e[i].v]>d[x]+e[i].w) { d[e[i].v]=d[x]+e[i].w; if(!inq[e[i].v]) { cnt++; if(cnt>((n+m)*2)) return 0; inq[e[i].v]=1; q.push(e[i].v); } } } } return 1; } int main() { double x,ll,uu,l,u; int i,j; while(~scanf("%d%d%lf%lf",&n,&m,&l,&u)) { memset(head,-1,sizeof head); h=0; ll=log(l);uu=log(u); for(i=0;i