> #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呢...,顺便贴代码 (1130) 70 2015-07-10 14:47:53