poj3259 最短路判环

题意：有一些点、一些道路和一些虫洞，道路是双向的，连接两点，花费正的时间，而虫洞是单向的，连接两点，可以使时间倒退，求是否能够回到过去。

只要明确回到过去其实就是当出现一个负环的时候，不断沿这个环走，就能够实现时间倒退了。

然后就是判负环……

spfa版：

 #include<stdio.h>

 #include<string.h>

 #include<queue>

 using namespace std;

 int head[],next[],point[],val[],size;

 int n,dis[],t[];

 bool vis[];

 void add(int a,int b,int v){

     int i;

     for(i=head[a];~i;i=next[i]){

         if(point[i]==b){

             if(val[i]>v)val[i]=v;

             return;

         }

     }

     point[size]=b;

     val[size]=v;

     next[size]=head[a];

     head[a]=size++;

 }

 void spfa(int s){

     memset(vis,,sizeof(vis));

     memset(dis,0x3f,sizeof(dis));

     memset(t,,sizeof(t));

     queue<int>q;

     dis[s]=;

     q.push(s);

     vis[s]=;

     t[s]++;

     int i;

     bool f=;

     while(!q.empty()&&f){

         int u=q.front();

         q.pop();

         vis[u]=;

         for(i=head[u];~i;i=next[i]){

             int j=point[i];

             if(dis[j]>dis[u]+val[i]){

                 dis[j]=dis[u]+val[i];

                 q.push(j);

                 t[j]++;

                 vis[j]=;

                 if(t[j]>n)f=;

             }

         }

     }

     if(f)printf("NO\n");

     else printf("YES\n");

 }

 int main(){

     int f;

     while(scanf("%d",&f)!=EOF){

         for(int q=;q<=f;q++){

             int w,m,i;

             scanf("%d%d%d",&n,&m,&w);

             memset(head,-,sizeof(head));

             size=;

             for(i=;i<=m;i++){

                 int a,b,v;

                 scanf("%d%d%d",&a,&b,&v);

                 add(a,b,v);

                 add(b,a,v);

             }

             for(i=;i<=w;i++){

                 int a,b,v;

                 scanf("%d%d%d",&a,&b,&v);

                 add(a,b,-v);

             }

             spfa();

         }

     }

     return ;

 }

bellman-fold版：

 #include<stdio.h>

 #include<string.h>

 int head[],next[],point[],val[],size=;

 int a,b,v,dis[],n;

 void add(int a,int b,int v){

     int i;

     for(i=head[a];~i;i=next[i]){

         if(point[i]==b){

             if(val[i]>v)val[i]=v;

             return;

         }

     }

     point[size]=b;

     val[size]=v;

     next[size]=head[a];

     head[a]=size++;

 }

 void bf(int s){

     int i,j,k;

     memset(dis,0x3f,sizeof(dis));

     dis[s]=;

     for(i=;i<=n-;i++){

         for(j=;j<=n;j++){

             for(k=head[j];~k;k=next[k]){

                 int p=point[k];

                 if(dis[p]>dis[j]+val[k]){

                     dis[p]=dis[j]+val[k];

                 }

             }

         }

     }

     bool f=;

     for(i=;i<=n;i++){

         for(j=head[i];~j;j=next[j]){

             int p=point[j];

             if(dis[p]>dis[i]+val[j]){

                 f=;

             }

         }

     }

     if(f)printf("YES\n");

     else printf("NO\n");

 }

 int main(){

     int f;

     while(scanf("%d",&f)!=EOF){

         for(int q=;q<=f;q++){

             int m,w;

             scanf("%d%d%d",&n,&m,&w);

             size=;

             memset(head,-,sizeof(head));

             int i;

             for(i=;i<=m;i++){

                 scanf("%d%d%d",&a,&b,&v);

                 add(a,b,v);

                 add(b,a,v);

             }

             for(i=;i<=w;i++){

                 scanf("%d%d%d",&a,&b,&v);

                 add(a,b,-v);

             }

             bf();

         }

     }

     return ;

 }