1 #include <cstring> 2 #include <cstdio> 3  4 #define dou double 5 #define INF 1<<29 6 #define MAX(a,b) ( a>b ?a :b ) 7  8 using namespace std; 9 10 const int N(10015);11 int n,m,s,u,v;12 dou money,uvr,uvl,vur,vul;13 int head[N],sumedge;14 struct Edge15 {16     int to,next;17     dou rate,lose;18     Edge(int to=0,int next=0,dou rate=0.00,dou lose=0.00) :19         to(to),next(next),rate(rate),lose(lose) {}20 }edge[N<<1];21 22 void ins(int from,int to,dou rate,dou lose)23 {24     edge[++sumedge]=Edge(to,head[from],rate,lose);25     head[from]=sumedge; 26 }27 28 dou change_money(dou x,dou rate,dou lose)29 {     return (x-lose)*rate ;    }30 31 int vis[N],if_YES;32 dou dis[N];33 34 void SPFA(int now)35 {36     vis[now]=1;37     if(if_YES) return ;38     for(int i=head[now];i;i=edge[i].next)39     {40         int go=edge[i].to;41         dou rate=edge[i].rate,lose=edge[i].lose;42         dou cmoney=change_money(dis[now],rate,lose);43         if(cmoney>dis[go])44         {45             if(vis[go])46             {47                 if_YES=true;48                 break ;49             }50             dis[go]=cmoney;51             SPFA(go);52         }53     }54     vis[now]=0;55     return ;56 }57 58 void init(int n)59 {60     if_YES=sumedge=0;61     memset(dis,0,sizeof(dis));62     memset(head,0,sizeof(head));63 }64 65 int main()66 {67 //    freopen("made.txt","r",stdin);68 //    freopen("myout.txt","w",stdout);69     70     while(~scanf("%d%d%d%lf",&n,&m,&s,&money))71     {72         if(s>n)73         {74             printf("NO\n");75             continue;76         }77         init(n);78         for(;m;m--)79         {80             scanf("%d%d%lf%lf%lf%lf",&u,&v,&uvr,&uvl,&vur,&vul);81             ins(u,v,uvr,uvl); ins(v,u,vur,vul);82         }83         dis[s]=money; SPFA(s);84         if(if_YES) printf("YES\n");85         else printf("NO\n");86     }87     return 0;88 }

 1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<queue> 6 using namespace std; 7 int u,v,w; 8 const int maxn = 1011; 9 const int maxm = 10011;10 const int oo = 1<<29;11 struct node12 {13     int u;14     int v;15     double x,y ;16     int next;17 }edge[maxm];18 double dis[maxn];19 int m,n,num;20 double ount;21 int head[maxn],cnt,sum[maxn];22 int vis[maxn] = {0};23 queue<int>qu;24 void add(int u,int v,double x,double y)25 {26     edge[cnt].u = u ;27     edge[cnt].v = v ;28     edge[cnt].x = x ;29     edge[cnt].y = y ;30     edge[cnt].next = head[u];31     head[u] = cnt++ ;32 }33 int spfa(int s)34 {35     for(int i = 0 ; i < m ; i++)36     {37         dis[i] = 0;38         vis[i] = 0 ;39     }40     dis[s] = ount;41     qu.push(s);42     vis[s] = 1 ;43     while(!qu.empty())44     {45         int u = qu.front();46         qu.pop();47         vis[u] = 0;48         for(int i = head[u] ; i != -1 ; i = edge[i].next)49         {50             int v = edge[i].v;51             if((dis[u]-edge[i].y)*edge[i].x > dis[v])52             {53                 dis[v] = (dis[u]-edge[i].y)*edge[i].x;54                 if(!vis[v])55                 {56                     vis[v] = 1;57                     qu.push(v);58                 }59                 sum[v]++;60                 if(sum[v] > m)61                 return -1;62             }63         }64     }65     return 1;66 }67 void Init()68 {69     cnt = 0 ;70     memset(head,-1,sizeof(head));71     memset(sum,0,sizeof(sum));72     while(!qu.empty())73     qu.pop();74 }75 int main()76 {77     freopen("made.txt","r",stdin);78     freopen("stdout.txt","w",stdout);79     80     while(scanf("%d %d %d %lf",&m,&n,&num,&ount)!=EOF)81     {82         Init();83         int u,v;84         double x,y,xx,yy ;85         for(int i = 0 ; i < n ; i++)86         {87             scanf("%d %d %lf %lf %lf %lf",&u,&v,&x,&y,&xx,&yy);88             add(u,v,x,y);89             add(v,u,xx,yy);90         }91         if(spfa(num) > 0)92         cout<<"NO"<<endl;93         else cout<<"YES"<<endl;94     }95     return 0;96 }