AcWing 904. 虫洞（SPFA or Djakarta or bellman判负环）

题目连接

http://poj.org/problem?id=3259

思路

大概是想问我们能不能找到一个负环，那么再看一眼数据范围，500，感觉乱搞都能过，但是出题人很恶心啊，n的范围并不是500，卡了巨久，但是用Floyd也是能过的，只不过写的时候要注意自己的常数，常数打了就过不了了，但是想到判负环我们应该联想到spfa和bellman算法，详情请看：spfa和bellman判负环,由于spfa算法是优化后的bellman所以我这里就不放bellman的代码了

代码 Floyd算法

#include
#include
#include
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1e3+10;

int n,m,w;
int f[N][N];

bool floyd(){
	for(int k = 1;k