POJ 3259 Wormholes(最短路Bellman_Ford)

Wormholes
 

大意:虫洞旅行,前面一部分(n组)是双向正权,后面一部分(w组)是单向负权,判断有没有负权环。

思路:由于有负权边,就不能Dijkstra了,用Bellman_Ford。就是看图中有没有负权环,有的话可以无限次走这个环,使得时间一定能得到一个负值。所以有的存在负环话就是可以,没有的话就是不可以了。


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Max = 10001

struct node
{
    int s, e, t;
} q[5010];

int dis[520];

bool Bellman_Ford(int n, int r)
{
    memset(dis, 0, sizeof(dis));
    for(int i = 1; i <= n; i++)
    {
        bool flag = false;
        for(int j = 1; j <= r; j++)
        {
            if(dis[q[j].e] > dis[q[j].s]+q[j].t)
            {
                dis[q[j].e] = dis[q[j].s]+q[j].t;
                flag = true;
            }
        }
        if(!flag)
        {
            break;
        }
    }
    for(int i = 1; i <= r; i++)
    {
        if(dis[q[i].e] > dis[q[i].s]+q[i].t)
        {
            return true;
        }
    }
    return false;
}

void Solve()
{
    int p, n, m, w, a, b, c;
    scanf("%d", &p);
    while(p--)
    {
        scanf("%d%d%d", &n, &m, &w);
        int r = 0;
        for(int i = 1; i <= m; i++)
        {
            scanf("%d%d%d", &a, &b, &c);
            q[++r].s = a;
            q[r].e = b;
            q[r].t = c;
            q[++r].s = b;
            q[r].e = a;
            q[r].t = c;
        }
        for(int i = 1; i <= w; i++)
        {
            scanf("%d%d%d", &a, &b, &c);
            q[++r].s = a;
            q[r].e = b;
            q[r].t = -c;
        }
        if(Bellman_Ford(n, r))
        {
            printf("YES\n");
        }
        else
        {
            printf("NO\n");
        }
    }
}

int main()
{
    Solve();

    return 0;
}


POJ 3259 Wormholes(最短路Bellman_Ford)

上一篇:poj3273


下一篇:hdu 1159 && poj 1458 Common Subsequence (LCS)