Tag: 负权环

POJ-3259 解题报告

题意简述 农夫共有F（1≤F≤5）个农场，每个农场有N块田（1 ≤ N ≤ 500）和M条普通无向路（1 ≤ M ≤ 2500），走过这些路需要一定时间。同时还存在W条有向虫洞（1 ≤ W ≤ 200），走这些虫洞可倒流一定时间。问对于各个农场，农夫是否有可能从某点出发，回到原点时时间早于出发时间。每个农场输出一行。可能则输出YES，否则为NO。