学步园

思路：原来以为 经过NE次松驰后，只要dis[src] > w 他就能赚钱
但想想这是错了。而应该是判断有没有存在正环 因为 可能NE次松驰后，dis[src] 没有大于w
但它存在正环，只要再继续松驰，就一定有dis[src] > w；

#include <stdio.h>
#define M 105
//#define inf 0x3f3f3f3f

int edgenum;
struct node
{
    int
v1,v2;
    double
rate,c;
} edge[M*M];

int bellman (int n,int src,double w)
{
    double
dis[M];
    int
i,j;
    for (i = 1;
i <= n; i ++)
       
dis[i] = 0;
    dis[src] =
w;
    for (i = 1;
i <= n; i ++)
    {
       
int finish = 0;
       
for (j = 1; j <= edgenum; j ++)
       
{
           
int u = edge[j].v1;
           
int v = edge[j].v2;
           
double r = edge[j].rate;
           
double c = edge[j].c;

           
if (dis[v] < (dis[u]-c)*r)
           
{
               
dis[v] = (dis[u]-c)*r;
               
finish = 1;
           
}
       
}
       
if (!finish)
break;           
//从别人那学来的优化
    }

    if (i ==
n+1)   
//存在正环
       
return 1;
    else
       
return 0;
}
int main ()
{
    int
n,m,s;
    int
i,j,k,u,v;
    double
cost,ruv,cuv,rvu,cvu;
    k = 0;
    scanf
("%d%d%d%lf",&n,&m,&s,&cost);

    while (m
--)
    {
       
scanf
("%d%d%lf%lf%lf%lf",&u,&v,&ruv,&cuv,&rvu,&cvu);

       
k++;