关于 Floyd 的卡常

众所周知，Floyd 是一个复杂度为 \(O(n^3)\) 的算法，通常用于求两点之间的最短路径。

其代码如下：

for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
		}
	}

在比赛和测试中，\(500 \leq n \leq 1000\) 的数据可能无法通过 Floyd 取得 \(\color{green}AC\) or 较不错的部分分，所以我们需要卡常。

卡常代码如下，与正常代码只有细微的差别。

for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			if(dp[i][k]==INF) continue;
			for(int j=1;j<=n;j++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
		}
	}

P2912 [USACO08OCT]Pasture Walking G

这是一道树上 LCA 问题，不过我们可以用 Floyd \(+\) 卡常通过此题。

非卡常 (\(\color{red}70\) 分)

卡常 (\(\color{green}AC\))

AC Code

#include<bits/stdc++.h>
using namespace std;
int n,q,dp[1001][1001];
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++) dp[i][j]=1e9;
	}
	for(int i=1;i<n;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		dp[x][y]=dp[y][x]=min(dp[x][y],z);
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			if(dp[i][k]==1e9) continue;
			for(int j=1;j<=n;j++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
		}
	}
	while(q--){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n",dp[x][y]);
	}
	return 0;
}