POJ 3259 Wormholes（SPFA）

时间：2021-05-30 16:45:53

http://poj.org/problem?id=3259

题意 ： 农夫约翰农场里发现了很多虫洞，他是个超级冒险迷，想利用虫洞回到过去，看再回来的时候能不能看到没有离开之前的自己，农场里有N块地，M条路连接着两块地，W个虫洞，连接两块地的路是双向的，而虫洞是单向的，去到虫洞之后时间会倒退T秒，如果能遇到离开之前的自己就输出YES，反之就是NO。

样例解释 ：

2

3 3 1

1 2 2

1 3 4

2 3 1

3 1 3

3 2 1

1 2 3

2 3 4

3 1 8

第一行中的2代表有两组测试数据，第一组测试数据中，3,3,1代表着有3块地，3条路，1个虫洞，下面三行代表着编号几到几的权值是几，最后一行代表的是通过虫洞去到目的地时间倒退了t秒

思路 ： 这个题因为去到虫洞时间会倒退，而走农场之间相连的路又会花掉时间，明显是判断有没有负环，只要有负环，他只要一直走就能回到过去，典型的Bellman-Ford做法，本题采用的是spfa做法。

 #include <cstdio>

 #include <cstring>

 #include <queue>

 #include<iostream>

 using namespace std;

 const int maxn = ;

 const int maxm = ;

 const int oo = <<;

 struct node

 {

     int u;

     int v;

     int w;

     int next;

 } edge[maxm];

 int dis[maxn];

 int cnt;

 int N,M,T;

 int head[maxn];

 bool vis[maxn];

 queue<int>qu;

 int count[maxn];

 void add(int u, int v, int w)

 {

     edge[cnt].u = u;

     edge[cnt].v = v;

     edge[cnt].w = w;

     edge[cnt].next = head[u];

     head[u] = cnt++;

 }

 int spfa(int s)

 {

     memset(count,,sizeof(count));

     for(int i = ; i <= N; i++)

     {

         dis[i] = oo;

         vis[i] = false;

     }

     dis[s] = ;

     qu.push(s);

     vis[s] = true;

     while(!qu.empty())

     {

         int u = qu.front();

         qu.pop();

         vis[u] = false;

         for(int i = head[u]; i != -; i = edge[i].next)

         {

             int v = edge[i].v;

             if(dis[u]+edge[i].w < dis[v])

             {

                 dis[v] = dis[u]+edge[i].w;

                 if(++count[v] > N) return ;

                 if(!vis[v])

                 {

                     vis[v] = true;

                     qu.push(v);

                 }

             }

         }

     }

     return ;

 }

 void init()

 {

     cnt = ;

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

 }

 int main()

 {

     int n ;

     scanf("%d",&n);

     while(n--)

     {

         init();

         scanf("%d %d %d",&N,&M,&T);

         int u, v, w;

         for(int i = ; i <= M; i++)

         {

             scanf("%d %d %d", &u, &v, &w);

             add(u, v, w);

             add(v, u, w);

         }

         for(int i =  ; i <= T ; i++)

         {

             cin>>u>>v>>w;

             add(u,v,(-*w));

         }

         int flag = spfa();

         if(flag == )

         cout<<"YES"<<endl;

         else

         cout<<"NO"<<endl;

     }

     return ;

 }

Bellman-Ford算法及其改进---SPFA算法可以参照下边这个博客

http://hi.baidu.com/laozhonggu/item/30a3f90d81b01fc975cd3c28

相关文章