简单的FLOYD。
for(i=0;i<N;i++) for(j=0;j<N;j++) if(f[j][i]<INF) /* <===这里! */ for(k=0;k<N;k++) if(f[i][k]<INF && f[j][i]+f[i][k]<f[j][k]) f[j][k]=f[j][i]+f[i][k];
有趣的是上面的标记的代码,有时这行代码使FLOYD加速,有时反倒拖慢速度。看起来这个剪枝的效率和输入有关。
/* * hdu-1869 * mike-w * 2012-4-7 */ #include<stdio.h> #include<stdlib.h> #include<string.h> #define MAX_SIZE 128 #define INF (1<<30) int f[MAX_SIZE][MAX_SIZE]; int N,M; int main(void) { #ifndef ONLINE_JUDGE freopen("in","r",stdin); #endif while(scanf("%d%d",&N,&M)!=EOF) { int i,j,k,e1,e2,flag; for(i=0;i<N;i++) for(j=0;j<N;j++) f[i][j]=INF; for(i=0;i<M;i++) scanf("%d%d",&e1,&e2),f[e1][e2]=f[e2][e1]=1; for(i=0;i<N;i++) for(j=0;j<N;j++) if(f[j][i]<INF) for(k=0;k<N;k++) if(f[i][k]<INF && f[j][i]+f[i][k]<f[j][k]) f[j][k]=f[j][i]+f[i][k]; flag=1; for(i=0;i<N;i++) for(j=i+1;j<N;j++) if(f[i][j]>7) flag=0,i=M,j=M; puts(flag?"Yes":"No"); } return 0; }