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 |
spfa,终于A了,WA了那么久,连妹纸的电话都不接。。。SPFA,AC之后才发现它比较水#include<queue> #include<stdio.h> #include<string.h> #define eps 1e-8 typedef struct line { int u,v,next; double c,r; }line; line e[10005]; double v,mon[300]; int next[300],count[300],all,n,m,s,vis[300]; using namespace std; queue<int>q; int sofa(int s) { int i,x; memset(mon,0,sizeof(mon)); memset(count,0,sizeof(count)); memset(vis,0,sizeof(vis)); mon[s]=v; vis[s]=1; count[s]++; q.push(s); while(!q.empty()) { x=q.front(); q.pop(); count[x]++; vis[x]=0; if (count[x]>=10*n)break; for(i=next[x];i!=-1;i=e[i].next) if(mon[e[i].v]<(mon[x]-e[i].c)*e[i].r) { mon[e[i].v]=(mon[x]-e[i].c)*e[i].r; if(0==vis[e[i].v]) { q.push(e[i].v); vis[e[i].v]=1; } } } if(mon[s]>=v+eps) return 1; return 0; } int main() { int i; while(scanf("%d%d%d%lf",&n,&m,&s,&v)!=EOF) { all=0; for(i=0;i<102;i++) next[i]=-1; int a,b;double rab,cab, rba,cba; for(i=0;i<m;i++) { scanf("%d%d",&a,&b); scanf("%lf%lf%lf%lf",&rab,&cab,&rba,&cba); e[all].u=a; e[all].v=b; e[all].r=rab; e[all].c=cab; e[all].next=next[a]; next[a]=all; all++; e[all].u=b; e[all].v=a; e[all].r=rba; e[all].c=cba; e[all].next=next[b]; next[b]=all; all++; } if(sofa(s))printf("YES\n"); else printf("NO\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator