警示后人 (如果你用floyd)
  • 板块P1613 跑路
  • 楼主rqrqwerwq
  • 当前回复1
  • 已保存回复1
  • 发布时间2025/5/16 06:30
  • 上次更新2025/8/5 16:46:14
查看原帖
警示后人 (如果你用floyd)
802813
rqrqwerwq楼主2025/5/16 06:30

初始化距离数组用倍增处理的时候。。。

错误:

 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逐层处理,第一种会错过有效信息。

2025/5/16 06:30
加载中...