poj 3259 Wormholes(最短路 Bellman)

题目：http://poj.org/problem?id=3259

题意：一个famer有一些农场，这些农场里面有一些田地，田地里面有一些虫洞，田地和田地之间有路，虫洞有这样的性质：时间倒流。问你这个农民能不能看到他自己，也就是说，有没有这样一条路径，能利用虫洞的时间倒流的性质，让这个人能在这个点出发前回去，这样他就是能看到他自己

典型的Bellman_ford 检查有没有形成负环。

套的模板

 #include <stdio.h>

 #include <string.h>

 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;

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

     edge[cnt].u = u;

     edge[cnt].v = v;

     edge[cnt++].w = w;

 }

 bool bellman_ford(int s){

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

         dis[i] = oo;

     }

     dis[s] = ;

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

         for(int j = ; j < cnt; j++){

             int u = edge[j].u;

             int v = edge[j].v;

             int w = edge[j].w;

             if(dis[v] > dis[u] + w){

                 dis[v] = dis[u] + w;

             }

         }

     }

     for(int j = ; j < cnt; j++){

         int u = edge[j].u;

         int v = edge[j].v;

         int w = edge[j].w;

         if(dis[v] > dis[u] + w){

             return false;

         }

     }

     return true;

 }

 void init(){

     cnt = ;

 }

 int main()

 {

     int t,x;

     scanf("%d",&t);

     while(t--)

     {

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

         int u, v, w;

         init();

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

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

             add(u, v, w);

             add(v, u, w);

         }

         while(x--)

         {

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

             add(u, v, -w);

         }

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

         else printf("YES\n");

     }

     return ;

 }

discuss里面还有spfa 的代码：http://poj.org/showmessage?message_id=162146

就是又设了一个cnt数组来记录各个点用过的次数，如果次数大于等于n说明有负环

巴特西

poj 3259 Wormholes(最短路 Bellman)

最新文章

热门文章