Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

spfa,终于A了,WA了那么久,连妹纸的电话都不接。。。SPFA,AC之后才发现它比较水

Posted by taojiaen at 2012-07-20 18:43:04 on Problem 1860
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator