poj 3259 时光穿梭问题 bellman_ford算法

题意：有n个空地，有m条双向大路，w条时光隧道单向路。问能否回到过去？

思路：判断是否有负环存在，如果有负环存在那么就可以一直小就可以回到过去了

1. 创建源顶点 V到其他顶点的距离d 初始为INF d[1]=0;
2. 计算最路径，执行v-1次遍历  对于每条边 if(d[v]>d[s]+t)  d[v]=d[s]+t;
3. 判断是否有负环   遍历所有的边 计算u至v的距离，如果对于v存在更小的距离 则存在
4. 有松弛 d[v]>d[u]+t

解决问题的代码：

#include <iostream>

#include <cstdio>

#include <algorithm>

using namespace std;

#define maxn 510

#define maxw 2550*2+510

#define INF 1000000

int d[maxn];

int n, m;

struct node {

        int u, v;

        int t;

}edge[maxw];

bool solve()

{

        for (int i = ; i <=n; i++) d[i] = INF;

        d[] = ;

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

        {

               bool flag = true;

               for (int j = ; j < m; j++)

               {

                       int u = edge[j].u;

                       int v = edge[j].v;

                       int t = edge[j].t;

                       if (d[v] > d[u] + t)

                       {

                              d[v] = d[u] + t;

                              flag = false;

                       }

               }

               if (flag) return false;

        }

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

        {

               if (d[edge[i].v] > d[edge[i].u] + edge[i].t)

                       return true;

        }

        return false;

}

int main()

{

        int t;

        scanf("%d", &t);

        while (t--)

        {

               int M, W;

               scanf("%d%d%d",&n, &M, &W);

               m = ;

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

               {

                       int u, v, t;

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

                       edge[m].u = u;

                       edge[m].v = v;

                       edge[m++].t = t;

                       edge[m].u = v;

                       edge[m].v = u;

                       edge[m++].t = t;

               }

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

               {

                       int u, v, t;

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

                       edge[m].u = u;

                       edge[m].v = v;

                       edge[m].t = -t;

               }

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

               else printf("NO\n");

        }

        return ;

}

其中比较神奇的是存图技巧