#include <cstdio>
//#include <queue>
//#include <deque>
#include <cstring>
using namespace std;
#define MAXM 202
#define MAXN 101
int n,m;
int first[MAXN];
int next[MAXM];
int pto[MAXM];
double earn[MAXM];
int start;
double d[MAXN];
double cost[MAXM];
bool vis[MAXM];
void addedge(int from,int to,double fromcost,double fromearn,int index){
    next[index]=first[from];
    pto[index]=to;
    cost[index]=fromcost;
    earn[index]=fromearn;
    first[from]=index;
}
bool input(){
    bool fl=false;
    memset(first,-1,sizeof(first));
   double double1;
    scanf("%d %d %d %lf",&n,&m,&start,&double1);
    d[start]=double1;
    double fromc,toc,frome,toe;
    int from,to;
    for(int i=0;i<m;i++){
        scanf("%d %d %lf %lf %lf %lf",&from,&to,&frome,&fromc,&toe,&toc);
        addedge(from,to,fromc,frome,2*i);
        addedge(to,from,toc,toe,2*i+1);
        if(from==start&&frome>0.999999){
            fl=true;
        }
        else if(to==start&&toe>0.999999){
            fl=true;
        }
    }
    return fl;
}
int que[MAXM];
int quehead;
int quetail;
void pushback(int inse){
    que[quetail]=inse;
    quetail=(quetail+1)%MAXM;
    vis[inse]=true;
}
void pushfront(int inse){
    quehead=(quehead-1+MAXM)%MAXM;
    que[quehead]=inse;
    vis[inse]=true;
}
int pop(){
    int ans=que[quehead];
    quehead=(quehead+1)%MAXM;
    vis[ans]=false;
    return ans;
}
bool find_loop(){
    if(!input())return false;
    pushback(start);
    while(quehead!=quetail){
        int from=pop();
        int p=first[from];
        while(p!=-1){
            int to=pto[p];
            double dtemp1;
            if((dtemp1=(d[from]-cost[p])*earn[p])>d[to]){
                d[to]=dtemp1;
                if(!vis[to]){
                    if(d[to]>d[que[quehead]])pushfront(to);
                    else pushback(to);
                }
                if(to==start){
                    return true;
                }
            }
            p=next[p];
        }
    }
    return false;
}
int main(){
    if(find_loop()){
        printf("YES\n");
    }
    else printf("NO\n");
}

• Re:只能优化到32ms?怎么优化到0ms呢...,顺便贴代码 (113) feidudu 2014-07-23 12:40:55
• Re:只能优化到32ms?怎么优化到0ms呢...,顺便贴代码 (2361) 70 2015-07-10 14:46:52
  • Re:只能优化到32ms?怎么优化到0ms呢...,顺便贴代码 (1130) 70 2015-07-10 14:47:53
• dfs的spfa判环 (1146) 70 2015-07-10 14:49:18