Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
1A随便嘚瑟一下/* *********************************************** *********************************** */ #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; struct edge { int u,v; double r,c; }; vector<edge>e; int N,M,S; double V; double d[2000]; bool bellman_ford(int src) { memset(d,0,sizeof(d)); d[src]=V; for(int i=0;i<N;i++) { int flg=0; for(int j=0;j<e.size();j++) { int u=e[j].u,v=e[j].v; double val=(d[u]-e[j].c)*e[j].r; if(val>d[v]){ d[v]=val; //printf("d[%d]=%lf\n",v,d[v]); flg=1; } } if(!flg) break; } for(int j=0;j<e.size();j++) { int u=e[j].u,v=e[j].v; double val=(d[u]-e[j].c)*e[j].r; if(val>d[v]) return true; } return false; } int main() { // freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); while(scanf("%d%d%d%lf",&N,&M,&S,&V)==4) { e.clear(); for(int i=0;i<M;i++) { //printf("i=%d\n",i); int u,v; scanf("%d%d",&u,&v); u--;v--; double rab,cab,rba,cba; scanf("%lf%lf%lf%lf",&rab,&cab,&rba,&cba); edge tmp; tmp.u=u;tmp.v=v;tmp.r=rab;tmp.c=cab; e.push_back(tmp); tmp.u=v;tmp.v=u;tmp.r=rba;tmp.c=cba; e.push_back(tmp); } if(bellman_ford(S-1)) puts("YES"); else puts("NO"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator