初始化距离数组用倍增处理的时候。。。
错误:
for(int k = 1; k <= n; k++){
for(int t = 0; t < 63; t++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(ndp[i][k][t] && ndp[k][j][t]){
ndp[i][j][t + 1] = 1;
dp[i][j] = 1;
}
}
}
}
}
正确:
for(int t = 0; t < 63; t++){
for(int k = 1; k <= n; k++){
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(ndp[i][k][t] && ndp[k][j][t]){
ndp[i][j][t + 1] = 1;
dp[i][j] = 1;
}
}
}
}
}
floyd需要按t逐层处理,第一种会错过有效信息。