| ||||||||||
| 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