poj 3259 (Bellman_Ford判断负环)

题意：John的农场里n块地，m条路连接两块地，k个虫洞，虫洞是一条单向路，不但会把你传送到目的地，而且时间会倒退Ts。我们的任务是知道会不会在从某块地出发后又回来，看到了离开之前的自己。

思路：虫洞连接的边是负权值的，如果途中存在一个负环的话，他可以沿着这个换一直走，时间肯定为负值。



#include<string.h>  
#include<stdio.h>  
const int N=510;  
const int inf=0x3fffffff;  
int start,num,n,dist[N];  
struct edge  
{  
    int st,ed,w;  
}e[6000];  
void addedge(int x,int y,int w)  
{  
    e[num].st=x;e[num].ed=y;e[num++].w=w;  
}  
int Bellman_Ford()  
{  
    int flag=0,i,u,v,j;  
    for(i=1;i<=n;i++)  
        dist[i]=inf;  
    dist[start]=0;  
    for(i=1;i<n;i++)//n-1次松弛  
    {  
        for(j=0;j<num;j++)  
        {  
            u=e[j].st;v=e[j].ed;  
            if(dist[v]>dist[u]+e[j].w)  
            {  
                dist[v]=dist[u]+e[j].w;  
                flag=1;  
            }  
        }  
        if(flag==0)break;  
    }  
    for(i=0;i<num;i++)  
        if(dist[e[i].ed]>dist[e[i].st]+e[i].w)//有负环  
            return 1;  
    return 0;  
}  
int main()  
{  
    int m,i,x,y,k,t,Case;  
    scanf("%d",&Case);  
    while(Case--)  
    {  
        scanf("%d%d%d",&n,&m,&k);  
        num=0;  
        for(i=1;i<=m;i++)  
        {  
            scanf("%d%d%d",&x,&y,&t);  
            addedge(x,y,t);  
            addedge(y,x,t);  
        }  
        for(i=0;i<k;i++)  
        {  
            scanf("%d%d%d",&x,&y,&t);  
            addedge(x,y,-t);  
        }  
        start=0;  
        if(Bellman_Ford())  
            printf("YES\n");  
        else printf("NO\n");  
    }  
    return 0;  
}

补充：软件开发 , C++ ,