英文理解起来有点累...很多农田,有的农田之间有路相连,从一个农田到另一个农田需要时间,然后有的农田中有虫洞,可以将你传送到另一个农场,并且时间会倒退..问FJ有没有可能在游历农场的过程中看到自己...
其实就是问有没有一个点,能在他从这个点出发前回到这个点,也就是求有没有负环.转了一圈后回到这个点时光倒退了,这样他在这个点等一会就能看到自己了..
求负环自然是Bellman-ford算法了..虫洞的边权为负值,为单向,但是农田之间路径是无向的.
#include <cstdio> using namespace std; struct Edge{ int s; int e; int w; }ed[5500]; int d[501]; int n,m,w,p; int bellman(){ int f,i=0; while(1){ f=0; for(int j=0;j<p;j++){ if(d[ed[j].e]>d[ed[j].s]+ed[j].w){ f=1; d[ed[j].e]=d[ed[j].s]+ed[j].w; } } if(f==0){//在n-1次内结束说明不存在负环 return 0; } if(i>n-1)return 1;//到N-1次还没结束说明存在负环 i++; } } int main(){ int nCase,s,e,t; scanf("%d",&nCase); while(nCase--){ p=0; scanf("%d%d%d",&n,&m,&w); for(int i=0;i<m;i++){ scanf("%d%d%d",&s,&e,&t); ed[p].s=s;ed[p].e=e;ed[p++].w=t; ed[p].s=e;ed[p].e=s;ed[p++].w=t; } for(int i=0;i<w;i++){ scanf("%d%d%d",&s,&e,&t); ed[p].s=s,ed[p].e=e,ed[p++].w=-t; } printf(bellman()?"YES\n":"NO\n"); } return 0; }