众所周知,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 \(+\) 卡常通过此题。
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;
}