题目连接

 

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

 

思路：用bellman-ford 判断有没有负权回路，如果有他就能看到自己。 不过，我认为应该判断每个点有没有负权回路，而不仅仅只判断第一个点就行了。

AC代码

#include 
    
     #include 
     
      #include 
      
       using namespace std;const int VM=520;const int EM=2600;const int INF=0x3f3f3f3f;struct Edge{    int u,v;    int cap;}edge[EM<<1];int n,m,k;int cnt,dis[VM];int Bellman(){    int i,j;    for(i=1;i<=n;i++)    {        dis[i]=INF;    }    dis[1]=0;    for(i=1;i<=n;i++)    {        for(j=1;j<=cnt-1;j++)        {            if(dis[edge[j].v]>dis[edge[j].u]+edge[j].cap)            {                dis[edge[j].v]=dis[edge[j].u]+edge[j].cap;            }        }    }    for(j=1;j
       
        dis[edge[j].u]+edge[j].cap)        {            return 0;        }    }    return 1;}int main(){    int t;    scanf("%d",&t);    while(t--)    {        scanf("%d%d%d",&n,&m,&k);        cnt=1;        int u,v,w;        while(m--)        {            scanf("%d%d%d",&u,&v,&w);            edge[cnt].u=u;            edge[cnt].v=v;            edge[cnt++].cap=w;            edge[cnt].u=v;            edge[cnt].v=u;            edge[cnt++].cap=w;        }        while(k--)        {            scanf("%d%d%d",&u,&v,&w);            edge[cnt].u=u;            edge[cnt].v=v;            edge[cnt++].cap=-w;        }        int ans=Bellman();        if(ans==0){            printf("YES\n");        }        else        {            printf("NO\n");        }    }    return 0;}