邻接矩阵版的Floyd，初始化

#define INF 0x3FFFFFFF
...
int d[MAXN][MAXN];
void init()
{
	...
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)
		{
			d[i][j]=INF;
		}
	}
	for(int i=1;i<=n;++i)
	{
		d[i][i]=0;
	}
	...
}

输入数据后，正常地跑Floyd

void solve()
{
	for(int k=1;k<=n;++k)
	{
		for(int i=1;i<=n;++i)
		{
			for(int j=1;j<=n;++j)
			{
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}
	...
}

最后出答案

void solve1()
{
	...
	for(int i=1;i<=n;++i)
	{
		if(d[i][i]<0&&d[1][i]!=INF)
		{
			cout<<"YES"<<endl;
			return;
		}
	}
	cout<<"NO"<<endl;
	return;
}

结果是WA#12。

哪里出错了呢？考虑这组数据：

1
3 2
2 3 -1
3 2 -1

显然地，在2->3->2存在负环，而1到2、3均无边，应输出NO。

然而按我这么写，输出结果会是YES。

让我们看向万恶之源：

d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

d[1][2]和d[1][3]均为INF，然而d[2][3]为-1!

当外层k循环跑到2时，对经过2的路径进行松弛，使得d[1][3]被松弛为INF-1。这意味着，带负权边时，两个不可及的点经Floyd松弛后的距离可能不为INF。即不应使用d[i][j]!=INF来判断不存在从i到j的路径。

现在来解决这个问题。

#define inf 0x1FFFFFFF
...
void solve1()
{
	...
	for(int i=1;i<=n;++i)
	{
		if(d[i][i]<0&&d[1][i]<inf)
		{
			...
		}
	}
	...
}

使用inf作为判断是否可达的边界。如果不可达，初值为INF的距离经过若干次松弛，应当大于等于inf。

这里的inf是随便设的。直觉上，如果INF可以作为极大，其一半也就可以作为极小。（考虑到不开辅助数组的2维Floyd可能在一轮松弛中反复计算某条负权边，如果可以被卡掉当我没说）

喜提60（？）。标算还得是SPFA。